레이팅 미적용JOI 高校では,
\(1 \times 1\) の正方形のタイルを使って \(N \times N\) の正方形の壁画を作り,
文化祭で展示することになった.
タイルの色は,赤,青,黄の 3 種類である.
壁画のデザインは次の通りである.
まず,最も外側の周に赤のタイルを貼り,その内側の周に青のタイルを貼る.
さらにその内側の周に黄色のタイルを貼る.
これを \(N \times N\) の正方形が埋め尽くされるまで繰り返す.
用いるタイルの色は,
一番外側の周から順番に赤,青,黄,赤,青,黄,...である.
文化祭が近づいてきたある日,
壁画のうち K 枚のタイルがはがれていることが判明した.
そこで,新しいタイルを購入して,はがれた箇所に新しいタイルを貼ることにした.
入力として壁画の一辺の長さ N と,
はがれたタイルの枚数 K,
K 枚のはがれたタイルの位置が与えられたとき,
はがれたタイルの色を求めるプログラムを作成せよ.
例えば,N = 11 の場合,\(11 \times 11\) の壁画のデザインは下図の通りである.
また,N = 16 の場合,\(16 \times 16\) の壁画のデザインは下図の通りである.
入力は全部で 2+K 行からなる.
1 行目には,壁画の一辺の長さ N (1 ≦ N ≦ 1000000000 = 10 9 )が,
2 行目には,はがれたタイルの枚数 K (\(1 \le K \le 1000\))が書かれている.
2+i 行目(\(1 \le i \le K\))には,2 つの整数 a i と b i (1 ≦ a i ≦ N, 1 ≦ b i ≦ N)が空白区切りで書かれており,
i 枚目のはがれたタイルが,
左から a i 列目,上から b i 行目のタイルであることを表す.
入力の 3 行目から 2+K 行目には同じタイルを表す行が重複して現れることはない.
また,与えられる入力データ 40% では, \(N \le 1000\) をみたしている.
出力は K 行からなる.
各行は 1 つの整数からなり,
i 行目(\(1 \le i \le K\))の整数は,i 枚目のはがれたタイルが赤のときは 1 を,青のときは 2 を,黄色のときは 3 を表す.
11
4
5 2
9 7
4 4
3 92
3
1
3