## Algorithm

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×n�×�. It is filled with numbers from 11 to n2�2 in the following way: the first n22⌈�22⌉ numbers from 11 to n22⌈�22⌉ are written in the cells with even sum of coordinates from left to right from top to bottom. The rest n2n22�2−⌈�22⌉ numbers from n22+1⌈�22⌉+1 to n2�2 are written in the cells with odd sum of coordinates from left to right from top to bottom. The operation xy⌈��⌉ means division x by y rounded up.

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

You are given q queries. The i-th query is described as a pair xi,yi��,��. The answer to the i-th query is the number written in the cell xi,yi��,�� (xi�� is the row, yi�� is the column). Rows and columns are numbered from 11 to n.

Input

The first line contains two integers n and q (1n1091≤�≤1091q1051≤�≤105) — the size of the board and the number of queries.

The next q lines contain two integers each. The i-th line contains two integers xi,yi��,�� (1xi,yin1≤��,��≤�) — description of the i-th query.

Output

For each query from 11 to q print the answer to this query. The answer to the i-th query is the number written in the cell xi,yi��,�� (xi�� is the row, yi�� is the column). Rows and columns are numbered from 11 to n. Queries are numbered from 11 to q in order of the input.

Examples
input
Copy
4 51 14 44 33 22 4
output
Copy
1816134
input
Copy
5 42 14 23 33 4
output
Copy
169720
Note

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

## Code Examples

### #1 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>

using namespace std;

long long n, q, x, y, o, e, oo, ee;

int main() {
scanf("%lld %lld", &n, &q);

if(n % 2 == 0)
o = e = n / 2;
else
o = n / 2 + 1, e = n / 2;

while(q-- != 0) {
scanf("%lld %lld", &x, &y);
long long bf = 0;

if((x + y) % 2 == 0)
oo = o, ee = e;
else
oo = e, ee = o;

long long xb = x - 1;
if(xb % 2 == 0)
bf = xb / 2 * oo + xb / 2 * ee;
else
bf = (xb / 2 + 1) * oo + xb / 2 * ee;

long long yb = y - 1;
bf += yb / 2;

if((x + y) % 2 == 0)
printf("%lld\n", bf + 1);
else
printf("%lld\n", ((1ll * n * n + 1) / 2) + 1 + bf);
}

return 0;
}
Copy The Code &

Input

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

Output

cmd
1
8
16
13
4