问题

在JOI高校中，决定使用 $1 \times 1$ 的正方形瓷砖来制作一个 $N \times N$ 的正方形壁画，并在文化祭上展示。瓷砖的颜色有红色、蓝色和黄色三种。壁画的设计如下：首先，在最外圈贴上红色瓷砖，然后在内圈贴上蓝色瓷砖，再在更内圈贴上黄色瓷砖。以此类推，直到填满 $N \times N$ 的正方形。使用的瓷砖颜色顺序是从最外圈开始依次为红色、蓝色、黄色、红色、蓝色、黄色...

一天，临近文化节，发现壁画中有 $K$ 块瓷砖脱落了。因此，决定购买新的瓷砖，并将其粘贴在脱落的位置上。

请编写一个程序，根据输入的壁画边长 $N$ 和脱落的瓷砖数量 $K$，以及脱落的 $K$ 块瓷砖的位置，求出脱落的瓷砖的颜色。

例如，当 $N = 11$ 时，$11 \times 11$ 的壁画如下图所示：

又例如，当 $N = 16$ 时，$16 \times 16$ 的壁画如下图所示：

输入

输入共有 $2 + K$ 行。第 $1$ 行为壁画的边长 $N$ ($1 \leqq N \leqq 1\,000\,000\,000 = 10^9$)，第 $2$ 行为脱落的瓷砖数量 $K$ ($1 \leqq K \leqq 1000$)。接下来 $K$ 行 ($1 \leqq i \leqq K$) 中的每行有两个整数 $a_i$ 和 $b_i$ ($1 \leqq a_i \leqq N, 1 \leqq b_i \leqq N$)，表示第 $i$ 块脱落的瓷砖在第 $a_i$ 列、第 $b_i$ 行。

$3$ 行到 $2 + K$ 行的输入中，不会出现相同的瓷砖位置行。另外，给定的输入数据中有 $40$% 的情况满足 $N \leqq 1\,000$。

输出

输出有 $K$ 行。每行一个整数，第 $i$ 行 ($1 \leqq i \leqq K$) 的整数表示第 $i$ 块脱落的瓷砖的颜色：红色用 $1$ 表示，蓝色用 $2$ 表示，黄色用 $3$ 表示。

输入示例 1

11
4
5 2
9 7
4 4
3 9

输出示例 1

2
3
1
3

在输入示例 1 中，$11 \times 11$ 的壁画如下图所示，× 表示脱落的瓷砖：

输入示例 2

16
7
3 7
5 2
11 6
15 2
9 7
8 12
15 16

输出示例 2

3
2
3
2
1
2
1