题目描述

如果把数 1, 2 , 3 , 4 , 5 , ... ,按照蛇形2放入 N*N 矩阵的左三角形中，然后有 M 个询问，每个询问为：

请计算第 x 行第 y 列的数是什么？

下面是 N=6 的 蛇形2 的图示

输入格式

第一行 2 个正整数： N , M ,范围在 [1,100000]。

下面有 M 行，每行 2 个整数，范围在 [1,N]。

输出格式

M 行，第 i 行是第 i 个询问的结果。如果相应坐标格子里没有填数字，输出 0 。

样例

3 4
1 1
2 2
2 3
3 2

1
2
0
5