Numbers on the Chessboard

You are given a chessboard of size $n \times n$ . It is filled with numbers from $1$ to $n^{2}$ in the following way: the first $⌈ \frac{n^{2}}{2} ⌉$ numbers from $1$ to $⌈ \frac{n^{2}}{2} ⌉$ are written in the cells with even sum of coordinates from left to right from top to bottom. The rest $n^{2} - ⌈ \frac{n^{2}}{2} ⌉$ numbers from $⌈ \frac{n^{2}}{2} ⌉ + 1$ to $n^{2}$ are written in the cells with odd sum of coordinates from left to right from top to bottom. The operation $⌈ \frac{x}{y} ⌉$ 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$ and the right board is the chessboard which is given for $n = 5$ .

$\text{[math]}$

You are given $q$ queries. The $i$ -th query is described as a pair $x_{i}, y_{i}$ . The answer to the $i$ -th query is the number written in the cell $x_{i}, y_{i}$ ( $x_{i}$ is the row, $y_{i}$ is the column). Rows and columns are numbered from $1$ to $n$ .

Input

The first line contains two integers $n$ and $q$ ( $1 \leq n \leq 10^{9}$ , $1 \leq q \leq 10^{5}$ ) — 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 $x_{i}, y_{i}$ ( $1 \leq x_{i}, y_{i} \leq n$ ) — description of the $i$ -th query.

Output

For each query from $1$ to $q$ print the answer to this query. The answer to the $i$ -th query is the number written in the cell $x_{i}, y_{i}$ ( $x_{i}$ is the row, $y_{i}$ is the column). Rows and columns are numbered from $1$ to $n$ . Queries are numbered from $1$ to $q$ in order of the input.

Examples

Input

Output

Input

Output

16
9
7
20

Solution

#include <bits/stdc++.h>

using namespace std;

int main() {

long long n, q;

cin >> n >> q;

while (q--) {

long long x, y;

cin >> x >> y;

long long ans = n * (x - 1) + y;

ans = (ans + 1) / 2;

long long sum = x + y;

ans += (sum % 2 == 1) ? (n * n + 1) / 2 : 0;

cout << ans << endl;

}

return 0;

}

Comments