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.