You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题陈述

给你一个大小为 $n \times n$ 的棋盘。从 $1$ 到 $\lceil \frac{n^2}{2} \rceil$ 的前 $\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$ 的棋盘。

给您提供了 $q$ 个查询。 $i$ -查询被描述为一对 $x_i, y_i$ 。 $i$ -th查询的答案是写在单元格 $x_i, y_i$ 中的数字（ $x_i$ 是行， $y_i$ 是列）。行和列的编号从 $1$ 到 $n$

输入格式

第一行包含两个整数 $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$ 个查询的描述。

输出格式

对于从 $1$ 到 $q$ 的每个查询，打印该查询的答案。 $i$ -查询的答案是写在单元格 $x_i, y_i$ 中的数字（ $x_i$ 是行， $y_i$ 是列）。行和列的编号范围为 $1$ 至 $n$ 。查询按输入顺序从 $1$ 到 $q$ 编号。

样例1

input

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

output

1
8
16
13
4

样例2

input

5 4
2 1
4 2
3 3
3 4

output

16
9
7
20

限制与约定

对于 $20\%$ 的数据，$n \le$ $100,$$q \le$ $min(10^5,n^2)$

对于 $50\%$ 的数据，$n \le$ $10^3,$$q \le$ $min(10^5,n^2)$

对于 $100\%$ 的数据，$n \le$ $10^9,$$q \le$ $min(10^5,n^2)$

• 时间限制: $1 s$
• 空间限制: $256 MB$