Problem Description

At JOI High School, they decided to create a mural for the school festival using $1 \times 1$ square tiles arranged in an $N \times N$ square pattern. There are three colors of tiles: red, blue, and yellow. The design of the mural is as follows: first, red tiles are placed on the outermost ring, then blue tiles on the next inner ring, followed by yellow tiles on the next inner ring. This process is repeated until the entire $N \times N$ square is filled. The colors of the tiles used follow the sequence: red, blue, yellow, red, blue, yellow, and so on.

As the school festival approached, it was discovered that $ K $ tiles had fallen off the mural. Therefore, new tiles need to be purchased and reattached to the fallen spots.

Given the side length of the mural $ N $, the number of fallen tiles $ K $, and the positions of the $ K $ fallen tiles, create a program to determine the color of each fallen tile.

For example, when $ N = 11 $, the design of the $11 \times 11$ mural is as shown in the figure below.

Also, when $ N = 16 $, the design of the $16 \times 16$ mural is as shown in the figure below.

Input Format

The input consists of $ 2 + K $ lines. The first line contains the side length of the mural $ N $ ($1 \leq N \leq 1,000,000,000 = 10^9$), and the second line contains the number of fallen tiles $ K $ ($1 \leq K \leq 1000$). The $ 2 + i $th line ($1 \leq i \leq K$) contains two integers $ a_i $ and $ b_i $ ($1 \leq a_i \leq N, 1 \leq b_i \leq N$), separated by a space, indicating that the $ i $th fallen tile is located in the $ a_i $th column from the left and the $ b_i $th row from the top.

The input from the third line to the $ 2 + K $th line does not contain duplicate lines representing the same tile. Also, 40% of the given input data satisfies $N \leq 1,000$.

Output Format

The output consists of $ K $ lines. Each line contains one integer, where the $ i $th line ($1 \leq i \leq K$) represents the color of the $ i $th fallen tile: $ 1 $ for red, $ 2 $ for blue, and $ 3 $ for yellow.

Sample Input and Output

Sample Input #1

11
4
5 2
9 7
4 4
3 9

Sample Output #1

2
3
1
3

Sample Input #2

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

Sample Output #2

3
2
3
2
1
2
1

Notes/Hints

Sample Explanation 1

In the first sample input, the $11 \times 11$ mural is as shown in the following figure, where × represents the fallen tiles.

见题面 Input 部分

见题面 Output 部分