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$$$.
您收到 $$$q$$$ 查询。 The $$$i$$$-th query is described as a pair $$$x_i, y_i$$$.第 $$$i$$$ 查询的答案是单元格 $$$x_i, y_i$$$ 中写入的数字($$$x_i$$$ 是行,$$$y_i$$$ 是列)。行和列的编号从 $$$1$$$ 到 $$$n$$$。
输入
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.
接下来的 $$$q$$$ 行每行包含两个整数。 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.
输出
For each query from $$$1$$$ to $$$q$$$ print the answer to this query.第 $$$i$$$ 查询的答案是单元格 $$$x_i, y_i$$$ 中写入的数字($$$x_i$$$ 是行,$$$y_i$$$ 是列)。行和列的编号从 $$$1$$$ 到 $$$n$$$。 Queries are numbered from $$$1$$$ to $$$q$$$ in order of the input.
示例
输入 #1
4 5 1 1 4 4 4 3 3 2 2 4
输出 #1
1 8 16 13 4
输入 #2
5 4 2 1 4 2 3 3 3 4
输出 #2
16 9 7 20
注意
示例中的疑问的答案位于问题陈述图片中的黑板上。