Задана шахматная доска размера $$$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 \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$$$ в порядке их описания во входных данных.
4 5
1 1
4 4
4 3
3 2
2 4
1
8
16
13
4
5 4
2 1
4 2
3 3
3 4
16
9
7
20
Ответы на запросы из тестовых примеров находятся на досках на картинке из условия задачи.
