Trường trung học JOI quyết định dùng những viên gạch hình vuông kích thước \(1 \times 1\) để tạo một bức tranh tường hình vuông kích thước \(N \times N\) và trưng bày trong lễ hội văn hóa. Có \(3\) màu gạch: đỏ, xanh lam và vàng.

Bức tranh được thiết kế như sau. Trước hết, lát vòng ngoài cùng bằng gạch đỏ, vòng ngay bên trong bằng gạch xanh lam, rồi vòng tiếp theo bằng gạch vàng. Tiếp tục lặp lại cho đến khi lát kín hình vuông \(N \times N\). Như vậy, màu các vòng từ ngoài vào trong lần lượt là đỏ, xanh lam, vàng, đỏ, xanh lam, vàng, \(\ldots\)

Một ngày khi lễ hội văn hóa đang đến gần, người ta phát hiện có \(K\) viên gạch của bức tranh bị bong ra. Vì vậy, họ quyết định mua gạch mới để lát lại những vị trí đó.

Chẳng hạn, khi \(N=11\), bức tranh kích thước \(11 \times 11\) có thiết kế như hình dưới đây.

Khi \(N=16\), bức tranh kích thước \(16 \times 16\) có thiết kế như hình dưới đây.

Yêu cầu

Cho độ dài cạnh \(N\) của bức tranh, số viên gạch bị bong \(K\) và vị trí của \(K\) viên gạch đó, hãy viết chương trình xác định màu của từng viên gạch bị bong.

Dữ liệu vào

Dữ liệu gồm \(2+K\) dòng:

• Dòng \(1\) chứa số nguyên \(N\), là độ dài cạnh của bức tranh.
• Dòng \(2\) chứa số nguyên \(K\), là số viên gạch bị bong.
• Dòng \(2+i\) (\(1 \le i \le K\)) chứa hai số nguyên \(a_i\) và \(b_i\), cách nhau bởi một dấu cách. Viên gạch bị bong thứ \(i\) nằm ở cột thứ \(a_i\) tính từ trái sang và hàng thứ \(b_i\) tính từ trên xuống.

Dữ liệu ra

In ra \(K\) dòng, mỗi dòng chứa một số nguyên. Trên dòng thứ \(i\) (\(1 \le i \le K\)), in 1 nếu viên gạch bị bong thứ \(i\) có màu đỏ, 2 nếu có màu xanh lam và 3 nếu có màu vàng.

Ràng buộc

• \(1 \le N \le 1\,000\,000\,000 = 10^9\).
• \(1 \le K \le 1000\).
• \(1 \le a_i \le N\) và \(1 \le b_i \le N\) với mọi \(1 \le i \le K\).
• Không có hai dòng trong các dòng từ \(3\) đến \(2+K\) mô tả cùng một viên gạch.

Phân nhóm

• Trong \(40\%\) dữ liệu đầu vào, \(N \le 1000\).

Ví dụ

11
4
5 2
9 7
4 4
3 9

2
3
1
3

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

3
2
3
2
1
2
1