题目描述

如果把数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