B. Numbers on the Chessboard

You are given a chessboard of size n×nn×n. It is filled with numbers from 11 to n2n2 in the following way: the first ⌈n22⌉⌈n22⌉numbers from 11 to ⌈n22⌉⌈n22⌉ are written in the cells with even sum of coordinates from left to right from top to bottom. The rest n2−⌈n22⌉n2−⌈n22⌉ numbers from ⌈n22⌉+1⌈n22⌉+1 to n2n2 are written in the cells with odd sum of coordinates from left to right from top to bottom. The operation ⌈xy⌉⌈xy⌉ means division xx by yy rounded up.

For example, the left board on the following picture is the chessboard which is given for n=4n=4 and the right board is the chessboard which is given for n=5n=5.

You are given qq queries. The ii-th query is described as a pair xi,yixi,yi. The answer to the ii-th query is the number written in the cell xi,yixi,yi (xixi is the row, yiyi is the column). Rows and columns are numbered from 11 to nn.

Input

The first line contains two integers nn and qq (1≤n≤1091≤n≤109, 1≤q≤1051≤q≤105) — the size of the board and the number of queries.

The next qq lines contain two integers each. The ii-th line contains two integers xi,yixi,yi (1≤xi,yi≤n1≤xi,yi≤n) — description of the ii-th query.

Output

For each query from 11 to qq print the answer to this query. The answer to the ii-th query is the number written in the cell xi,yixi,yi (xixi is the row, yiyi is the column). Rows and columns are numbered from 11 to nn. Queries are numbered from 11 to qq in order of the input.

Examples

input

4 5
1 1
4 4
4 3
3 2
2 4

output

1
8
16
13
4

input

5 4
2 1
4 2
3 3
3 4

output

16
9
7
20

题意：在n*n的格子里填数字，每个格子的坐标x+y如果是偶数就输出这是第几个偶数，如果是奇数就输出这是第几个奇数+最后一个格子的数字。

规律在于对n的奇偶性和x+y的奇偶性判定

代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
#define closeio std::ios::sync_with_stdio(false)
#define mem(a,b) memset(a,b,sizeof(a))

int main()
{
	ll n,m,i;
	cin>>n>>m;
	while(m--)
	{
		ll x,y,num;
		cin>>x>>y;
		if(n%2==0)
		{
			num=(x-1)*(n/2)+((y+1)/2);
			if((x+y)%2==0)
				cout<<num<<endl;
			else
				cout<<num+n*n/2<<endl;
		}
		else
		{
			num=((x-1)*n+y+1)/2;
			if((x+y)%2==0)
				cout<<num<<endl;
			else
				cout<<num+n*n/2+1<<endl;
		}
	}
	return 0;
}

CF的ID终于有颜色了，离红名dalao又进了一步(ಡωಡ)