Barchin và Charos đang chơi một trò chơi trên một lưới gồm \(2N \times 2M\) ô vuông đơn vị. Các hàng được đánh số từ \(0\) đến \(2N - 1\) từ trên xuống dưới, và các cột được đánh số từ \(0\) đến \(2M - 1\) từ trái sang phải. Với \(0 \le i < 2N\) và \(0 \le j < 2M\), ta ký hiệu ô ở hàng \(i\) và cột \(j\) là \((i, j)\).

Barchin đưa cho Charos lần lượt \(N \cdot M\) khối. Mỗi khối là một hình vuông \(2 \times 2\) gồm bốn viên gạch \(1 \times 1\). Barchin đã tô màu đen hoặc trắng cho mọi viên gạch trong khối, đồng thời đảm bảo rằng ít nhất một viên gạch có màu trắng.

Charos phải đặt mỗi khối lên lưới ngay lập tức sau khi nhận được, mà không biết mình sẽ nhận được những khối nào sau đó. Các khối không thể xoay. Mỗi khối phải được đặt hoàn toàn bên trong lưới, che phủ chính xác bốn ô lưới. Hơn nữa, viên gạch trên cùng bên trái của mỗi khối phải che phủ một ô có tọa độ hàng và cột đều là số chẵn. Mỗi ô trong lưới phải được bao phủ bởi tối đa một khối.

Barchin thắng trò chơi nếu, sau khi bất kỳ khối nào được đặt xuống, tồn tại một hình vuông \(2 \times 2\) gồm các ô được phủ bởi bốn viên gạch đen. Một cách hình thức, nếu các ô \((a, b)\), \((a + 1, b)\), \((a, b + 1)\), \((a + 1, b + 1)\) đều được phủ bởi các viên gạch đen với \(0 \le a < 2N - 1\) và \(0 \le b < 2M - 1\), thì Barchin thắng. Các chỉ số \(a\) và \(b\) không cần phải là số chẵn.

Charos thắng nếu cô ấy đặt tất cả \(N \cdot M\) khối mà không để Barchin thắng. Lưu ý rằng việc đặt \(N \cdot M\) khối sẽ phủ kín toàn bộ lưới.

Nhiệm vụ của bạn là cài đặt một chiến lược để Charos giành chiến thắng trong trò chơi. Có thể chứng minh rằng, với các điều kiện ràng buộc đã cho, Charos luôn có thể sắp xếp các khối sao cho đảm bảo chiến thắng, bất kể màu sắc của các khối mà cô ấy nhận được sau này là gì.

Chi tiết cài đặt

Bạn cần cài đặt hai hàm sau:

void init(int N, int M)

• N: bằng một nửa số hàng trong lưới.
• M: bằng một nửa số cột trong lưới.
• Hàm này được gọi đúng một lần cho mỗi trường hợp test, ngay khi bắt đầu thực thi chương trình của bạn.

std::pair<int, int> receive_block(int TL, int TR, int BL, int BR)

• TL, TR, BL, BR: lần lượt là màu của các viên gạch góc trên bên trái, góc trên bên phải, góc dưới bên trái và góc dưới bên phải của khối hiện tại, như được minh họa trong hình dưới đây. Mỗi giá trị có thể là \(0\) (trắng) hoặc \(1\) (đen).
• Hàm này được gọi chính xác \(N \cdot M\) lần cho mỗi trường hợp test, sau lần gọi ban đầu đến hàm init.

Hàm này phải trả về một cặp số nguyên \((i, j)\), trong đó \(i\) là tọa độ hàng và \(j\) là tọa độ cột của ô mà viên gạch góc trên bên trái của khối này sẽ được đặt vào. Cả \(i\) và \(j\) đều phải là số chẵn, và vùng \(2 \times 2\) được khối này che phủ không được chồng chéo lên bất kỳ khối nào đã được đặt trước đó.

Nếu receive_block trả về một cặp số không thỏa mãn các yêu cầu này, hoặc nếu sau khi đặt khối, một ô vuông \(2 \times 2\) các ô bị che phủ hoàn toàn bởi các viên gạch màu đen, trình chấm điểm sẽ ngay lập tức kết thúc chương trình của bạn và kết quả cho trường hợp test sẽ là Output isn't correct.

Hành vi của hệ thống chấm điểm là không thích ứng. Điều này có nghĩa là chuỗi các khối mà Barchin giao cho Charos đã được xác định trước khi hàm init được gọi.

Các ràng buộc

Với mỗi khối, gọi \(S\) là số viên gạch màu đen trong bốn viên của khối đó. Tức là, \(S = TL + TR + BL + BR\).

• \(1 \le N, M \le 100\).
• \(0 \le S \le 3\) cho mỗi khối.

Các subtask

Ví dụ

Xét một trò chơi với \(N = 1\) và \(M = 2\), do đó lưới có \(2\) hàng và \(4\) cột. Trình chấm đầu tiên gọi:

init(1, 2)

Ban đầu, tất cả các ô đều trống. Lưới trông như sau:

Có \(N \cdot M = 2\) khối cần đặt. Giả sử Barchin đưa ra một khối gồm ba viên gạch đen và một viên gạch trắng ở góc trên bên phải. Trình chấm gọi:

receive_block(1, 0, 1, 1)

Charos quyết định đặt khối này ở phía bên trái của lưới bằng cách trả về \((0, 0)\).

Lưới bây giờ trông như sau:

Sau đó, Barchin đưa ra một khối khác gồm ba viên gạch đen và một viên gạch trắng ở góc trên bên trái:

receive_block(0, 1, 1, 1)

Ô duy nhất còn lại có hàng chẵn và cột chẵn có thể đóng vai trò là góc trên bên trái của khối \(2 \times 2\) là \((0, 2)\), vì vậy Charos trả về \((0, 2)\). Lưới cuối cùng sẽ như sau:

Không có ô vuông \(2 \times 2\) được phủ kín hoàn toàn bằng các viên gạch màu đen, vì vậy Charos đã đặt thành công tất cả các khối mà Barchin không bao giờ thắng. Charos thắng trò chơi.

Trình chấm mẫu

Định dạng dữ liệu vào:

N M
TL[0] TR[0] BL[0] BR[0]
TL[1] TR[1] BL[1] BR[1]
...
TL[NM-1] TR[NM-1] BL[NM-1] BR[NM-1]

Định dạng kết quả ra:

R[0] C[0]
R[1] C[1]
...
R[NM-1] C[NM-1]

Trong đó, \(R[k]\) và \(C[k]\) là cặp số nguyên được trả về bởi lần gọi thứ \(k\) của hàm receive_block.

Nguồn: Đề bài chính thức IOI 2026, bản tiếng Việt (VNM), ngày 1 — Tiling Game (tiling).