Codeforces-B. Numbers on the Chessboard

B. Numbers on the Chessboard

题目链接

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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

Copy

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

output

Copy

1
8
16
13
4

input

Copy

5 4
2 1
4 2
3 3
3 4

output

Copy

16
9
7
20

Note

Answers to the queries from examples are on the board in the picture from the problem statement.

题意：查找询问位置点的数字大小。

归类：数论。

记：很多数论的题目看起来情况很多，但是只要把同样的部分处理后，特别处理不同的地方的细节即可。把复杂问题简单化。

题解：分成几部分分别求解即可。

1.先分为（x+y）的结果是奇数还是偶数，偶数说明在第一轮就填上数字了，奇数表示在第二轮才被填上需要加上总数的一半。

2.若在第一轮上就被填上了，则需要知道经过几次完整的行，即 ((x-1)/2)*n ，再加上剩余的行数，即 ((x+1)%2)*(n/2+n%2)，再加上y的数值，即 y/2+y%2。

3.第二轮被填上同样处理即可。

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long int n,t;
	cin>>n>>t;
	while(t--)
	{
		long long int x,y;
		cin>>x>>y;
		if((x+y)%2==0)			//第一轮的情况
			cout<<((x-1)/2)*n+(((x+1)%2)*(n/2+n%2)+y/2+y%2)<<endl;
		else					//第二轮的情况
			cout<<(n*n)/2+n%2+((x-1)/2)*n+(((x+1)%2)*(n/2)+(y)/2+(y)%2)<<endl;
	}
}