낚시

건덕이는 일감호에 딸린 작은 섬, 와우도에 앉아 세월을 낚아 올리는 중이다.

일감호는 $N\times M$ 공간으로 나타낼 수 있다. 공간은 $1\times 1$ 크기의 정사각형 칸으로 나누어져 있고, 각 칸에는 물고기가 여럿 존재한다. 가장 수심이 깊으면서 건덕이로부터 가장 먼 칸은 $\left( N,M \right)$이다.

건덕이는 낚싯대를 휘둘러 원하는 칸에 미끼를 던질 수 있다. 무게가 $a$인 무게추를 매달아 $b$만큼의 힘으로 낚싯대를 휘두르면 $\left( a,b \right)$ 칸에 미끼가 존재하게 된다.

미끼는 일감호 공간 안에서 물고기들을 사로잡는데, 그 대상은 미끼가 속한 칸으로부터 수면까지 존재하는 모든 칸에 있는 물고기들이다. 즉, $\left( a,b \right)$에 존재하는 미끼는 $1\leq i\leq a$인 모든 정수 $i$에 대해서 $\left( i,b \right)$에 존재하는 모든 물고기를 사로잡는다.

건덕이가 낚싯줄을 한 바퀴 감아올리면, $\left( a,b \right)$에 위치한 미끼는 $\left( a-1,b-1 \right)$로 이동하며, 이동한 위치에서 물고기를 사로잡는다. 미끼가 일감호의 공간을 벗어나면 즉시 회수된다.

건덕이가 무게추의 무게와 낚싯대를 휘두를 힘을 알려줄 때마다, 낚싯대를 휘두른 뒤 회수할 때까지 낚싯줄을 감아올리면 몇 마리의 물고기가 사로잡힐지 구해줘야 한다. 건덕이가 많은 물고기를 잡을 수 있도록 도와주자!

첫째 줄에 일감호의 크기를 나타내는 정수 $N,M$과 건덕이가 낚싯대를 휘두를 횟수 $Q$가 공백으로 구분되어 주어진다. $\left( 1\leq N,M\leq 2\\, 000;\ 1\leq Q\leq 300\\, 000 \right)$

둘째 줄부터 $N$개의 줄에 걸쳐 각 공간에 존재하는 물고기의 수 $A\_{ij}$가 주어진다. $N$개의 줄 중 $i$번째 줄에 있는 $j$번째 수는 $(i,j)$ 칸에 물고기가 $A\_{ij}$마리 존재한다는 의미다. $\left( 0\leq A\_{ij}\leq 500 \right)$

$N+2$번째 줄부터 $Q$개의 줄에 걸쳐 건덕이가 미끼에 매달 무게추의 무게를 나타내는 정수 $W\_i$와 낚싯대를 휘두르는 힘을 나타내는 정수 $P\_i$가 공백으로 구분되어 주어진다. $\left( 1\leq W\_i\leq N;\ 1\leq P\_i\leq M \right)$

$Q$개의 줄에 걸쳐, 각 낚시에 대해서 미끼를 회수할 때까지 몇 마리의 물고기가 사로잡히는지 출력한다.

입출력의 양이 많으므로, 빠른 입출력을 사용하는 것을 권장합니다. 대표적인 언어에 따른 빠른 입출력은 아래를 참고하세요.

• C++: cin, cout을 사용하는 경우 입출력 전에 cin.tie(nullptr); ios::sync_with_stdio(false);를 한 번 적용해야 합니다. 줄 바꿈할 때는 endl 대신 '\n'을 사용해야 합니다.
• Java: BufferedReader와 BufferedWriter를 사용해야 합니다.
• Python3, PyPy3: input() 대신 sys.stdin.readline().rstrip()을 사용해야 합니다.