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

输入/输出例子1

输入：

3 4

1 1

2 2

2 3

3 2

输出：

1 

2 

0

5 

中级课程