Đường Đi Đối Xứng

Cho một lưới kích thước $n\times n$ với $n$ lẻ. Các hàng được đánh số từ $1$ đến $n$ từ trên xuống dưới, các cột được đánh số từ $1$ đến $n$ từ trái sang phải. Ô nằm ở giao của hàng $x$ và cột $y$ được ký hiệu là $(x,y)$.

Mỗi ô chứa số $0$ hoặc số $1$. Bạn chỉ biết trước rằng ô góc trên bên trái chứa $1$ và ô góc dưới bên phải chứa $0$, tức là $a_{1,1}=1$ và $a_{n,n}=0$.

Nhiệm vụ của bạn là xác định toàn bộ nội dung của lưới bằng cách đặt câu hỏi cho hệ thống.

Một đường đi đơn điệu từ ô $(x_1,y_1)$ đến ô $(x_2,y_2)$ là dãy ô bắt đầu ở $(x_1,y_1)$, kết thúc ở $(x_2,y_2)$, mỗi bước chỉ đi sang phải hoặc đi xuống. Đường đi đó được gọi là đối xứng nếu dãy các chữ số ghi trên các ô của nó đọc xuôi và đọc ngược giống hệt nhau.

Mỗi câu hỏi cho biết giữa hai ô đã chọn có tồn tại ít nhất một đường đi đơn điệu đối xứng hay không. Lưu ý rằng giữa hai ô thường có nhiều đường đi đơn điệu, và hệ thống chỉ trả lời "có" hoặc "không", chứ không cho biết đường đi nào.

Giao thức tương tác

Đây là bài toán tương tác. Chương trình của bạn giao tiếp với hệ thống đánh giá qua đầu vào/ra chuẩn.

Đầu tiên, chương trình đọc số nguyên lẻ $n$.

Sau đó bạn có thể thực hiện hai loại thao tác:

• ? x1 y1 x2 y2: hỏi về cặp ô $(x_1,y_1)$ và $(x_2,y_2)$. Bộ bốn số phải thỏa mãn $1\le x_1\le x_2\le n$, $1\le y_1\le y_2\le n$ và $x_1+y_1+2\le x_2+y_2$ (hai ô phải đi được từ ô thứ nhất tới ô thứ hai bằng các bước sang phải và xuống dưới, đồng thời không kề nhau). Hệ thống trả lời $1$ nếu tồn tại đường đi đơn điệu đối xứng từ $(x_1,y_1)$ đến $(x_2,y_2)$, và trả lời $0$ nếu không tồn tại.
• !: khai báo kết quả. Sau dòng chứa dấu !, in ra $n$ dòng, dòng thứ $i$ là xâu độ dài $n$ mô tả hàng thứ $i$ của lưới, rồi kết thúc chương trình.

Bạn được phép dùng tối đa $n^2$ câu hỏi dạng ?.

Nếu một câu hỏi không hợp lệ hoặc bạn vượt quá số câu hỏi cho phép, hệ thống sẽ in ra $-1$ và dừng tương tác; khi đó chương trình của bạn phải thoát ngay lập tức.

Quan trọng: sau mỗi lần in ra, bạn phải flush output:

• C++: cout << endl; hoặc cout.flush();
• Python: print(..., flush=True)

Ràng buộc

• $3\le n<50$, $n$ lẻ
• $a_{1,1}=1$, $a_{n,n}=0$
• Số câu hỏi tối đa: $n^2$

Ví dụ