낚시

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

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

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

미끼는 일감호 공간 안에서 물고기를 사로잡는다. 대상은 미끼가 있는 칸부터 수면까지 있는 모든 칸의 물고기다. 즉, $(a,b)$에 있는 미끼는 $1\leq i\leq a$인 모든 정수 $i$에 대해 $(i,b)$에 있는 모든 물고기를 사로잡는다.

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

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

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

둘째 줄부터 $N$개의 줄에 걸쳐 각 공간에 있는 물고기의 수 $A_{ij}$가 주어진다. $i$번째 줄의 $j$번째 수는 $(i,j)$ 칸에 물고기가 $A_{ij}$마리 있다는 뜻이다. ($0\leq A_{ij}\leq 500$)

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

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

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

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