Задана шахматная доска размера \(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\).
Выходные данные
Для каждого запроса от \(1\) до \(q\) выведите ответ на него. Ответом на \(i\)-й запрос является число, записанное в клетке \(x_i, y_i\) (\(x_i\) это строка, \(y_i\) это столбец). Строки и столбцы пронумерованы от \(1\) до \(n\). Запросы пронумерованы от \(1\) до \(q\) в порядке их описания во входных данных.
Примечание
Ответы на запросы из тестовых примеров находятся на досках на картинке из условия задачи.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 5
1 1
4 4
4 3
3 2
2 4
|
1
8
16
13
4
|
|
2
|
5 4
2 1
4 2
3 3
3 4
|
16
9
7
20
|