CF1027B.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 $\lceil \frac{n^2}{2} \rceil$ numbers from $1$ to $\lceil \frac{n^2}{2} \rceil$ are written in the cells with even sum of coordinates from left to right from top to bottom. The rest $n^2 - \lceil \frac{n^2}{2} \rceil$ numbers from $\lceil \frac{n^2}{2} \rceil + 1$ to $n^2$ are written in the cells with odd sum of coordinates from left to right from top to bottom. The operation $\lceil\frac{x}{y}\rceil$ 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$.

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$.

给你一个 $n \times n$ 的棋盘。棋盘按如下方式填入 $1$ 到 $n^2$ 的数字：
前 $\lceil \frac{n^2}{2} \rceil$ 个数（即 $1$ 到 $\lceil \frac{n^2}{2} \rceil$）按从左到右、从上到下的顺序，填入所有行列坐标之和为偶数的格子中；
其余 $n^2 - \lceil \frac{n^2}{2} \rceil$ 个数（即 $\lceil \frac{n^2}{2} \rceil + 1$ 到 $n^2$）同样按从左到右、从上到下的顺序，填入所有行列坐标之和为奇数的格子中。
其中，$\lceil\frac{x}{y}\rceil$ 表示将 $x$ 除以 $y$ 后向上取整。

例如，下图中左侧棋盘对应 $n=4$ 的情况，右侧棋盘对应 $n=5$ 的情况。

你将收到 $q$ 个查询。第 $i$ 个查询由一对坐标 $(x_i, y_i)$ 描述。第 $i$ 个查询的答案即为第 $x_i$ 行、第 $y_i$ 列（行号与列号均从 $1$ 开始编号）格子中所填的数字。

The first line contains two integers $n$ and $q$ ($1 \le n \le 10^9$, $1 \le q \le 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 \le x_i, y_i \le n$) — description of the $i$-th query.

第一行包含两个整数 $n$ 和 $q$（$1 \le n \le 10^9$，$1 \le q \le 10^5$）—— 分别表示棋盘的大小和查询次数。

接下来的 $q$ 行每行包含两个整数。第 $i$ 行包含两个整数 $x_i, y_i$（$1 \le x_i, y_i \le n$）—— 描述第 $i$ 次查询。

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.

对于从 $1$ 到 $q$ 的每个查询，请输出该查询的答案。第 $i$ 个查询的答案为位于第 $x_i$ 行、第 $y_i$ 列的单元格中所写的数字（其中 $x_i$ 表示行号，$y_i$ 表示列号）。行号与列号均从 $1$ 编号至 $n$。查询按输入顺序编号，从 $1$ 到 $q$。

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

示例中查询的答案在题目描述图片中的黑板上。