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$.
<center></center>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 \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.
## 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.
[samples]
## Note
Answers to the queries from examples are on the board in the picture from the problem statement.
你被给定一个大小为 $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$ 中的数字（$x_i$ 是行，$y_i$ 是列）。行和列的编号从 $1$ 到 $n$。
第一行包含两个整数 $n$ 和 $q$（$1 lt.eq n lt.eq 10^9$，$1 lt.eq q lt.eq 10^5$）——棋盘的大小和查询的数量。
接下来的 $q$ 行每行包含两个整数。第 $i$ 行包含两个整数 $x_i, y_i$（$1 lt.eq x_i, y_i lt.eq n$）——描述第 $i$ 个查询。
对于每个从 $1$ 到 $q$ 的查询，请输出该查询的答案。第 $i$ 个查询的答案是写在格子 $x_i, y_i$ 中的数字（$x_i$ 是行，$y_i$ 是列）。行和列的编号从 $1$ 到 $n$。查询按输入顺序编号为 $1$ 到 $q$。
示例中查询的答案如题目描述中的图所示。
## Input
第一行包含两个整数 $n$ 和 $q$（$1 lt.eq n lt.eq 10^9$，$1 lt.eq q lt.eq 10^5$）——棋盘的大小和查询的数量。接下来的 $q$ 行每行包含两个整数。第 $i$ 行包含两个整数 $x_i, y_i$（$1 lt.eq x_i, y_i lt.eq n$）——描述第 $i$ 个查询。
## Output
对于每个从 $1$ 到 $q$ 的查询，请输出该查询的答案。第 $i$ 个查询的答案是写在格子 $x_i, y_i$ 中的数字（$x_i$ 是行，$y_i$ 是列）。行和列的编号从 $1$ 到 $n$。查询按输入顺序编号为 $1$ 到 $q$。
[samples]
## Note
示例中查询的答案如题目描述中的图所示。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the size of the chessboard.
Let $ C = \{ (x, y) \mid x, y \in \{1, \dots, n\} \} $ be the set of cells.
For a cell $ (x, y) $, define its *coordinate parity* as $ p(x, y) = (x + y) \bmod 2 $.
Let $ m = \left\lceil \frac{n^2}{2} \right\rceil $.
**Partitioning Rule**
- Cells with $ p(x, y) = 0 $ (even sum) are assigned numbers from $ 1 $ to $ m $.
- Cells with $ p(x, y) = 1 $ (odd sum) are assigned numbers from $ m+1 $ to $ n^2 $.
**Ordering Rule**
Numbers are assigned in row-major order (left to right, top to bottom), skipping cells not matching the parity condition.
**Objective**
For each query $ (x_i, y_i) $, compute the number $ f(x_i, y_i) $ written in cell $ (x_i, y_i) $, defined as:
Let $ s = x_i + y_i $.
Let $ k $ be the number of cells $ (a, b) $ with $ 1 \le a \le x_i $, $ 1 \le b \le n $, and $ (a, b) \preceq (x_i, y_i) $ in row-major order, such that $ p(a, b) = p(x_i, y_i) $.
Then:
$$
f(x_i, y_i) =
\begin{cases}
k & \text{if } s \equiv 0 \pmod{2} \\
m + k & \text{if } s \equiv 1 \pmod{2}
\end{cases}
$$
**Efficient Computation**
Let $ \text{count\_parity}(x, y, p) $ denote the number of cells $ (a, b) $ with $ a \le x $, $ b \le y $, and $ p(a, b) = p $, in row-major order up to $ (x, y) $.
This can be computed as:
Let $ \text{total\_up\_to}(x, y) = (x - 1) \cdot n + y $
Let $ \text{even\_count\_up\_to}(x, y) = \left\lfloor \frac{\text{total\_up\_to}(x, y) + 1 - (x + y) \bmod 2}{2} \right\rfloor $
Then:
- If $ p(x, y) = 0 $, then $ k = \text{even\_count\_up\_to}(x, y) $
- If $ p(x, y) = 1 $, then $ k = \text{total\_up\_to}(x, y) - \text{even\_count\_up\_to}(x, y) $
Thus:
$$
f(x, y) =
\begin{cases}
\left\lfloor \dfrac{(x - 1)n + y + 1 - (x + y) \bmod 2}{2} \right\rfloor & \text{if } (x + y) \equiv 0 \pmod{2} \\
m + \left( (x - 1)n + y - \left\lfloor \dfrac{(x - 1)n + y + 1 - (x + y) \bmod 2}{2} \right\rfloor \right) & \text{if } (x + y) \equiv 1 \pmod{2}
\end{cases}
$$