Mảnh đất trồng cây (mdtrongcay.*)

Được vua cha cho một miếng đất phía tây thành phố, Po quyết định lấy một phần đất hình vuông có kích thước \(n \times n\) để làm vườn trồng cây, phần đất này được Po chia thành \(n\) dòng và \(n\) cột, các dòng được đánh số thứ tự từ 1 đến \(n\) từ trên xuống dưới, các cột được đánh số thứ tự từ 1 đến \(n\) từ trái qua phải, ô ở dòng \(i\) cột \(j\) được gọi là ô \((i,j)\). Trên mỗi ô, Po trồng một loại cây khác nhau, các loại cây được đánh số hiệu từ 1 đến \(n^{2}\);

Po trồng cây vào các ô theo quy luật như sau:

- Đầu tiên, Po chia vườn thành 4 phần đều nhau, mỗi phần có \(\frac{n^{2}}{4}\) ô:

+ Phần 1 gồm các ô ở phía trên bên trái, chọn các loại cây có số hiệu nhỏ nhất để trồng;

+ Phần 2 gồm các ô ở phía trên bên phải, chọn các loại cây có số hiệu nhỏ nhất chưa trồng ở Phần 1 để trồng;

+ Phần 3 gồm các ô ở phía dưới bên phải, chọn các loại cây có số hiệu nhỏ nhất chưa trồng ở Phần 1 và Phần 2 để trồng;

+ Phần 4 gồm các ô ở phía dưới bên trái, chọn các cây có số hiệu lớn nhất để trồng;

- Tiếp theo, với mỗi phần, Po tiếp tục chia nhỏ thành 4 phần và chọn loại cây trồng theo quy luật như trên cho đến khi mỗi phần có kích thước \(1 \times 1\) thì thực hiện trồng cây.

Ví dụ với \(n = 4\), loại cây trồng ở mỗi ô như hình:

	1	2	3	4
1	1	2	5	6		Phần 1 trồng 4 loại cây: 1, 2, 3, 4
2	4	3	8	7		Phần 2 trồng 4 loại cây: 5, 6, 7, 8
3	13	14	9	10		Phần 3 trồng 4 loại cây: 9, 10, 11, 12
4	16	15	12	11		Phần 4 trồng 4 loại cây: 13, 14, 15, 16

Sau một thời gian mưa thuận gió hòa, cây trồng phát triển tươi tốt. Vua cha biết tin rất vui mừng nên vi hành đến thăm Po đồng thời đưa ra hai loại câu hỏi:

• Loại 1: Hãy cho biết loại cây \(c\) được trồng ở ô nào?

• Loại 2: Hãy cho biết ô \((x,y)\) đang trồng loại cây gì?

Yêu cầu: Hãy giúp Po trả lời các câu hỏi của vua cha.

Dữ liệu vào:

- Dòng đầu tiên ghi số nguyên dương \(n\ (2 \leq n \leq 10^{9})\);

- Dòng thứ 2 ghi số nguyên dương \(q\ (q \leq 10^{5})\) cho biết số lượng câu hỏi của vua cha;

- \(q\) dòng tiếp theo, mỗi dòng ghi 2 hoặc 3 số nguyên dương có dạng:

1 \(c\): tương ứng với câu hỏi loại 1 \((c \leq n^{2})\); hoặc

2 \(x\ y\): tương ứng với câu hỏi loại 2 \((1 \leq x,y \leq n)\).

Dữ liệu vào luôn đảm bảo tồn tại cách trồng cây thỏa yêu cầu đề bài.

Kết quả:

- In ra \(q\) dòng tương ứng với câu trả lời của \(q\) câu hỏi theo đúng thứ tự trong Dữ liệu vào.

Ví dụ:

Dữ liệu vào	Kết quả		Dữ liệu vào	Kết quả
4 2 2 3 4 1 8	10 2 3		8 4 1 4 2 3 4 1 15 2 5 7	2 1 10 4 2 37

Ràng buộc:

- Subtask 1 (10% số điểm): \(n = 2\);

- Subtask 2 (20% số điểm): \(n \leq 8\);

- Subtask 3 (30% số điểm): \(n \leq 1000\) và \(q \leq 10\);

- Subtask 4 (15% số điểm): chỉ có câu hỏi loại 1;

- Subtask 5 (15% số điểm): chỉ có câu hỏi loại 2;

- Subtask 6 (10% số điểm): không có ràng buộc gì thêm.