← 返回题目列表

Codeforces · 1027/B

B. 棋盘上的数字

中文机器翻译题面 查看原题

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

注意

示例中的疑问的答案位于问题陈述图片中的黑板上。