AT_joi2011yo_c タイル (Tile)

[problemUrl]: https://atcoder.jp/contests/joi2011yo/tasks/joi2011yo_c 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 $ を表す． - - - - - -

### Sample Explanation 1 入力例 $ 1 $ において，$ 11\ \times\ 11 $ の壁画は以下の図の通りである．`×` は，はがれたタイルを表す． !\[2011-yo-t3-fig03.png\](https://img.atcoder.jp/joi2011yo/2011-yo-t3-fig03.png) - - - - - -