Fishing

Geondeok sits on Warudo, a small island attached to Ilgam Lake, reeling in time.

Ilgam Lake can be represented as an $N\times M$ grid. The grid is divided into $1\times 1$ square cells, and each cell holds several fish. The cell that is the deepest and farthest from Geondeok is $(N,M)$.

Geondeok can swing a fishing rod to throw bait into any cell he wants. If he attaches a sinker of weight $a$ and swings the rod with strength $b$, bait is placed in cell $(a,b)$.

The bait catches fish inside the lake grid. It catches all fish in every cell from the cell where the bait sits up to the surface. In other words, bait at $(a,b)$ catches all fish in $(i,b)$ for every integer $i$ with $1\leq i\leq a$.

When Geondeok reels the line in by one turn, the bait at $(a,b)$ moves to $(a-1,b-1)$ and catches the fish in its new cell. If the bait leaves the lake grid, it is retrieved immediately.

Each time Geondeok gives a sinker weight and a swing strength, find how many fish are caught by the time the bait is retrieved after the swing and reeling in. Help Geondeok catch as many fish as possible!

The first line contains the integers $N,M$ for the lake size and $Q$, the number of times Geondeok swings the rod, separated by spaces. ($1\leq N,M\leq 2\,000$; $1\leq Q\leq 300\,000$)

From the second line through the $N$ lines that follow, the number of fish $A_{ij}$ in each cell is given. The $j$-th number on the $i$-th line means cell $(i,j)$ has $A_{ij}$ fish. ($0\leq A_{ij}\leq 500$)

From line $N+2$ through the $Q$ lines that follow, the integer $W_i$, the weight of the sinker Geondeok attaches to the bait, and the integer $P_i$, the strength of the swing, are given separated by a space. ($1\leq W_i\leq N$; $1\leq P_i\leq M$)

For each of the $Q$ fishing attempts, print on its own line how many fish are caught before the bait is retrieved.

Since the input is large, fast I/O is recommended. Fast I/O for common languages is shown below.

• C++: When using cin and cout, you must call cin.tie(nullptr); ios::sync_with_stdio(false); once before any I/O. For a newline, use '\n' instead of endl.
• Java: You must use BufferedReader and BufferedWriter.
• Python3, PyPy3: Use sys.stdin.readline().rstrip() instead of input().