問題

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