螺旋方阵

题目描述

把整数 $1$ 到 $n^2$ 按顺时针螺旋的顺序填入一个 $n$ 行 $n$ 列的方阵：从左上角 $(1, 1)$ 开始填 $1$，然后向右走，遇到已经填过的格子或方阵边界就顺时针转 $90$ 度继续填，直到填满。填完后有 $q$ 次询问，每次给出 $r$ 与 $c$，问方阵中第 $r$ 行第 $c$ 列填的是哪个数。

输入格式

第一行两个整数 $n$ 与 $q$。

接下来 $q$ 行，每行两个整数 $r$ 与 $c$。行列号都从 $1$ 开始。

输出格式

$q$ 行，每行一个整数，依次对应每次询问的答案。

样例

输入样例

3 2
2 2
3 1

输出样例

9
7

样例解释

$n = 3$ 时方阵为 $\begin{pmatrix}1&2&3\\8&9&4\\7&6&5\end{pmatrix}$，所以 $(2,2)$ 填的是 $9$，$(3,1)$ 填的是 $7$。

数据范围

$1 \le n \le 2000$，$1 \le q \le 10^5$，$1 \le r, c \le n$。