D. Interesting Snake Queue
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A snake queue can be formed as an $$$n \cdot n$$$ grid graph.

When someone enter this queue, he is in position $$$(1,1)$$$.

Assume someone is in $$$(i,j)$$$ currently(and $$$(i,j)$$$ is not the endpoint of the queue),one second later:

  • If $$$i$$$ is odd and $$$j \neq n$$$,he'll move to $$$(i,j+1)$$$;
  • If $$$i$$$ is odd and $$$j = n$$$,he'll move to $$$(i+1,j)$$$;
  • If $$$i$$$ is even and $$$j \neq 1$$$,he'll move to $$$(i,j-1)$$$;
  • If $$$i$$$ is even and $$$j = 1$$$,he'll move to $$$(i+1,j)$$$.

There're $$$n \cdot n$$$ people.The $$$i_{th}$$$ person has a number $$$a_i$$$ in hi hand.In the $$$j_{th}(1\leq j \leq n^2)$$$ second,the $$$j_{th}$$$ person will enter this queue.

For example,$$$n=3$$$ and $$$a=[11,22,33,44,55,66,77,88,99]$$$,the following images show the status of the snake queue at certain times:

The status in the $$$2_{nd},5_{th}$$$ and $$$8_{th}$$$ second,respectively.

You need to answer the $$$q$$$ queries.The $$$i_{th}$$$ query gives two integers $$$t_i,x_i$$$,which means you need to answer the sum of the numbers of all the people in the $$$x_{th}$$$ column in the $$$t_{th}$$$ second.

Input

The first line of contains two integers $$$n,q$$$ ($$$2 \le n \le 2000$$$,$$$1 \le q \le 10^6$$$).

The second line of contains $$$n \cdot n$$$ integers $$$a_1,a_2,...,a_{n^2}(1 \leq a_i \leq 2000)$$$.

The next $$$q$$$ lines,the $$$i_{th}$$$ line contains two integers $$$t_i,x_i(1 \leq t_i \leq n^2,1 \leq x_i \leq n)$$$,which means you need to answer the sum of the numbers of all the people in the $$$x_{th}$$$ column in the $$$t_{th}$$$ second.

Output

For each query, print a single integer in a new line — the sum of the numbers of all the people in the $$$x_{th}$$$ column in the $$$t_{th}$$$ second.

Example
Input
3 7
11 22 33 44 55 66 77 88 99
2 1
2 3
5 2
5 3
8 1
8 2
8 3
Output
22
0
55
55
143
132
121