Mirko rất thích những hình vẽ trên đồng ruộng, được tạo nên từ cây cỏ bị ép rạp và được cho là tác phẩm của người ngoài hành tinh. Một đêm hè, cậu quyết định tự tạo một hình như vậy trên đồng cỏ của bà. Là người yêu nước, Mirko chọn phần hình bàn cờ trên quốc huy Croatia: một bàn cờ \(5\times5\) gồm \(13\) ô vuông đỏ và \(12\) ô vuông trắng xen kẽ nhau.

Đồng cỏ là một hình vuông được chia thành \(N\times N\) ô. Ô ở góc dưới bên trái có tọa độ \((1,1)\), còn ô ở góc trên bên phải có tọa độ \((N,N)\).

Mirko chọn một số nguyên lẻ \(M\ge3\). Mỗi ô vuông của bàn cờ chiếm một khối \(M\times M\) ô của đồng cỏ, với các cạnh song song với các cạnh đồng cỏ. Toàn bộ bàn cờ nằm trọn trong đồng cỏ. Cậu chỉ ép rạp cỏ trong các ô vuông đỏ và giữ nguyên tất cả phần cỏ còn lại.

Sau khi Mirko đi ngủ, tác phẩm của cậu thu hút sự chú ý của những người ngoài hành tinh thật sự. Từ tàu vũ trụ phía trên đồng cỏ, họ khảo sát hình vẽ bằng một thiết bị đơn giản: thiết bị chỉ có thể xác định cỏ trong một ô cụ thể có bị ép rạp hay không.

Họ đã tìm được một ô có cỏ bị ép rạp và muốn xác định ô chính giữa hình vẽ để ngắm nhìn tác phẩm. Họ không biết kích thước \(M\) của các ô vuông trên bàn cờ.

Cho kích thước \(N\), tọa độ \((X_0,Y_0)\) của một ô có cỏ bị ép rạp và khả năng tương tác với thiết bị, hãy tìm tọa độ ô chính giữa hình vẽ. Bạn được sử dụng thiết bị không quá \(300\) lần trong mỗi lần chạy trên một bộ dữ liệu.

Tương tác

Đây là bài toán tương tác. Chương trình gửi lệnh qua đầu ra chuẩn và đọc phản hồi của thiết bị từ đầu vào chuẩn.

Khi bắt đầu, đọc ba số nguyên \(N,X_0,Y_0\) trên một dòng, phân cách bởi một dấu cách. \(N\) là kích thước đồng cỏ; \((X_0,Y_0)\) là tọa độ một ô có cỏ bị ép rạp.

Để kiểm tra ô \((X,Y)\), ghi một dòng có dạng examine X Y. Các tọa độ phải thỏa mãn \(1\le X,Y\le N\). Nếu tọa độ nằm ngoài đồng cỏ hoặc chương trình gửi quá \(300\) lệnh examine, chương trình nhận \(0\) điểm cho bộ dữ liệu đó.

Thiết bị trả lời bằng một dòng chứa từ true nếu cỏ trong ô \((X,Y)\) bị ép rạp, hoặc từ false nếu không.

Khi đã tìm được ô chính giữa, ghi một dòng có dạng solution XC YC, trong đó \((X_C,Y_C)\) là tọa độ ô đó. Chương trình sẽ được tự động kết thúc ngay khi xuất lời giải.

Các từ lệnh và phản hồi phải được viết đúng chữ thường như trên. Sau mỗi lần ghi ra đầu ra chuẩn, phải đẩy dữ liệu khỏi bộ đệm (flush) để bộ chấm nhận được lệnh.

Ràng buộc

• \(15\le N\le 2\,000\,000\,000\).
• \(1\le X_0,Y_0\le N\); cỏ tại ô \((X_0,Y_0)\) được bảo đảm bị ép rạp.
• \(M\) là số nguyên lẻ, \(M\ge3\); bàn cờ kích thước \(5M\times5M\) nằm trọn trong đồng cỏ.
• Không quá \(300\) lệnh examine trong mỗi lần chạy trên một bộ dữ liệu.
• Mỗi bộ dữ liệu có một đáp án đúng duy nhất, cố định và không phụ thuộc vào những câu hỏi chương trình đặt ra.

Chấm điểm trên hệ thống

Lưu ý: Cách chia nhóm và tính điểm dưới đây là bản điều chỉnh để luyện tập trên hệ thống, không khẳng định tương đương cách chấm tại IOI gốc.

Mỗi nhóm được chấm độc lập: chỉ nhận điểm của nhóm khi vượt qua tất cả bộ kiểm thử trong nhóm; nếu có bộ kiểm thử không đạt thì nhóm nhận 0 điểm. Tổng điểm tối đa là 100.

Nhãn nhóm là phần số trong tên tệp dữ liệu gốc. Tất cả tệp cùng nhãn, kể cả các hậu tố chữ và pf, đều thuộc nhóm đó.

Các ví dụ trong đề không tính điểm.

Ví dụ

19 7 4
true
false
false
true

examine 11 2
examine 2 5
examine 9 14
examine 18 3
solution 12 9

Nguồn

IOI 2007.