1540. Stamps Under a Modulus
A grid of R by C zeros is given, together with a modulus m. Then q
stamps arrive, each r1 c1 r2 c2 v, meaning "add v to every cell of the
rectangle from (r1, c1) to (r2, c2) inclusive". The value v may be
negative.
Print the final grid with every entry reduced MODULO m into the range
0 to m - 1.
``` R = 2, C = 3, m = 5, stamps (1 1 2 2 3) and (2 2 2 3 4)
raw 3 3 0 -> mod 5 3 3 0 3 7 4 3 2 4 ```
``` R = 3, C = 4, m = 7, stamps (1 1 3 4 -3) and (2 2 2 3 -5)
raw -3 -3 -3 -3 -> mod 7 4 4 4 4 -3 -8 -8 -3 4 6 6 4 -3 -3 -3 -3 4 4 4 4 ```
R = 2, C = 2, m = 1, one stamp of 999999999 -> every cell is 0
## What most people try first
Walking every cell of every rectangle. One stamp can cover the whole grid, so
2 * 10^5 stamps over a 1000 by 1000 grid is 2 * 10^11 writes. Problem 736
solves that with a two-dimensional difference array, and this problem is the
same machinery with one extra demand at the end.
## The four corner marks, then one recovery pass
``` d[r1][c1] += v d[r1][c2+1] -= v d[r2+1][c1] -= v d[r2+1][c2+1] += v
then d[i][j] += d[i-1][j] + d[i][j-1] - d[i-1][j-1] ```
The fourth mark returns the region beyond both closers, which the two subtractions removed twice.
## The reduction that most languages get wrong
In C, C++, Java and JavaScript the remainder operator keeps the SIGN of the
left operand, so -1 % 3 is -1 and not 2. Printing that directly gives a
value outside the required range. The fix is
((value % m) + m) % m
which is correct for positive values too and costs one extra remainder. In Python the operator already returns a non-negative result for a positive modulus, and this is one of the few places where the languages genuinely disagree on an answer rather than on syntax.
The second sample exists entirely for this: every raw value is negative.
## Why a difference array survives being reduced
Addition modulo m is still associative and still has inverses, so the whole
argument for the four marks and the recovery pass goes through unchanged. The
reduction can therefore be applied at every step, or once at the end, and the
answers agree. Reducing at every step keeps the numbers small; reducing once at
the end keeps the code simple, and the values stay well inside 64 bits either
way.
## The modulus of one
m = 1 makes every answer 0, whatever was stamped. It is the cheapest check
that the reduction is applied at all rather than only when the raw value looks
too big.
## Overflow
Up to 2 * 10^5 stamps of magnitude 10^9 can land on one cell, reaching
2 * 10^14 before any reduction. That is far past the 2147483647 a signed
32 bit integer holds, so the difference grid and the recovery pass are 64 bit.
Three such stamps already reach 3 * 10^9, which is also past it.
## Cost
O(q + R C) time and O(R C) memory.
Constraints - `1 ≤ R ≤ 1000` - `1 ≤ C ≤ 1000` - `0 ≤ q ≤ 200000` - `1 ≤ m ≤ 10^9` - `1 ≤ r1 ≤ r2 ≤ R` and `1 ≤ c1 ≤ c2 ≤ C` - `-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 four integers R, C, q and m.
Each of the next q lines contains five integers r1, c1, r2, c2 and v.
Output
Print the final grid as R lines of C integers each, separated by single spaces. Every printed value must lie between 0 and m - 1 inclusive, even when the raw total is negative.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.