1543. Stamps That Wrap Around
A grid of R by C zeros is given on a TORUS: walking off the right edge
arrives back at column 1, and walking off the bottom arrives back at row 1.
Then q stamps arrive, each r1 c1 h w v, meaning "add v to the h by w
block whose top-left cell is (r1, c1), wrapping where it runs off an edge".
Print the final grid.
``` R = 3, C = 4, stamps (2 3 2 3 1) and (1 1 1 1 5)
5 0 0 0 the first stamp covers rows 2 and 3, and columns 3, 4 and 1, 1 0 1 1 because column 5 wraps back to column 1 1 0 1 1 ```
R = 3, C = 4, one stamp (1 1 3 4 2) -> every cell is 2
R = 4, C = 4, one stamp (4 4 1 1 9) -> only the far corner holds 9
## What most people try first
Two nested loops with a modulo on each index. One stamp can cover the whole
grid, so 2 * 10^5 stamps over a 1000 by 1000 grid is 2 * 10^11 writes.
The second reflex is to apply the four-corner stamp of problem 736 with the
corners taken modulo the grid size. That is wrong in a way worth seeing: after
wrapping, c2 can be SMALLER than c1, and the four-mark scheme then
describes a rectangle with inverted sides, which adds and subtracts v over
regions that bear no relation to the intended block.
## A wrapped block is at most four ordinary blocks
Split the row range and the column range independently.
rows: [r1 .. min(r1+h-1, R)] and, if r1+h-1 > R, [1 .. r1+h-1-R]
columns: [c1 .. min(c1+w-1, C)] and, if c1+w-1 > C, [1 .. c1+w-1-C]
Each range splits into one or two pieces, so the block splits into one, two or four axis-aligned rectangles. Stamp each of them with the ordinary four marks and recover once at the end.
## Why the pieces are disjoint and cover the block exactly
The row range of a wrapped block is a set of h distinct rows, because h is
at most R. Cutting it at the bottom edge gives the rows at or below r1 and
the rows that wrapped, and no row is in both precisely because there are at
most R of them. The same holds for columns. The block is the product of the
two ranges, so the up-to-four rectangles are the products of the pieces:
disjoint, and together the whole block.
If h were allowed to exceed R the block would lap the torus and a row would
be covered twice, which no decomposition into distinct rectangles expresses.
That is why the constraints cap h at R and w at C.
## The corner that exercises every branch
The stamp (4, 4, 1, 1, v) on a 4 by 4 grid wraps in neither direction and its
closing marks land at row 5 and column 5, both outside. The stamp (2, 3, 2, 3)
on a 3 by 4 grid wraps in columns only. A stamp at (3, 3) with h = 2 and
w = 2 on a 3 by 3 grid wraps in both and produces all four pieces.
## Overflow
Up to 2 * 10^5 stamps of magnitude 10^9 can land on one cell, reaching
2 * 10^14, far past the 2147483647 a signed 32 bit integer holds, so the
difference grid is 64 bit. Three such stamps already reach 3 * 10^9, which is
also past it.
## Cost
O(q + R C) time, since each stamp costs at most sixteen marks, and
O(R C) memory. Problem 1535 answers the QUERY version of the same wrap, and
tiles the grid two by two instead of splitting the region; both are ways of
turning a wrapped shape into ordinary rectangles.
Constraints - `1 ≤ R ≤ 1000` - `1 ≤ C ≤ 1000` - `0 ≤ q ≤ 200000` - `1 ≤ r1 ≤ R` and `1 ≤ c1 ≤ C` - `1 ≤ h ≤ R` and `1 ≤ w ≤ C`, so no stamp laps the torus - `-10^9 ≤ v ≤ 10^9` - when `q` is 0 no stamp line follows at all - `R` and `C` are independent; the grid need not be square
Input
The first line contains three integers R, C and q.
Each of the next q lines contains five integers r1, c1, h, w and v.
Output
Print the final grid as R lines of C integers each, separated by single spaces. The shape is R by C and cells no stamp reaches are printed as 0.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.