配点: 100 点
問題
在JOI高中,1 \times 1 的托盘瓷砖被用来制作 N \times N 雕像的图案,并在文化节上展示。瓷砖的颜色有红色、蓝色、黄色。 3 该种类的壁画设计如下。首先,在最外围铺红色瓷砖,然后在其内层铺蓝色瓷砖。再在内层铺黄色瓷砖。如此循环,直到 N \times N 的托盘被填满。使用瓷砖的颜色,从最外围开始顺序为红、蓝、黄、红、蓝、黄,\ldots 。从
某天文化节临近时,发现壁画中有 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)。2 + i 行目 (1 \leqq i \leqq K) 中,2 整数 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 行组成。每行由 1 个整数构成,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