codeforces#P1205C. Palindromic Paths

Palindromic Paths

Description

This is an interactive problem

You are given a grid n×nn\times n, where nn is odd. Rows are enumerated from 11 to nn from up to down, columns are enumerated from 11 to nn from left to right. Cell, standing on the intersection of row xx and column yy, is denoted by (x,y)(x, y).

Every cell contains 00 or 11. It is known that the top-left cell contains 11, and the bottom-right cell contains 00.

We want to know numbers in all cells of the grid. To do so we can ask the following questions:

"?? x1x_1 y1y_1 x2x_2 y2y_2", where 1x1x2n1 \le x_1 \le x_2 \le n, 1y1y2n1 \le y_1 \le y_2 \le n, and x1+y1+2x2+y2x_1 + y_1 + 2 \le x_2 + y_2. In other words, we output two different cells (x1,y1)(x_1, y_1), (x2,y2)(x_2, y_2) of the grid such that we can get from the first to the second by moving only to the right and down, and they aren't adjacent.

As a response to such question you will be told if there exists a path between (x1,y1)(x_1, y_1) and (x2,y2)(x_2, y_2), going only to the right or down, numbers in cells of which form a palindrome.

For example, paths, shown in green, are palindromic, so answer for "?? 11 11 22 33" and "?? 11 22 33 33" would be that there exists such path. However, there is no palindromic path between (1,1)(1, 1) and (3,1)(3, 1).

Determine all cells of the grid by asking not more than n2n^2 questions. It can be shown that the answer always exists.

The first line contains odd integer (3n<503 \le n < 50) — the side of the grid.

Interaction

You begin the interaction by reading nn.

To ask a question about cells (x1,y1),(x2,y2)(x_1, y_1), (x_2, y_2), in a separate line output "?? x1x_1 y1y_1 x2x_2 y2y_2".

Numbers in the query have to satisfy 1x1x2n1 \le x_1 \le x_2 \le n, 1y1y2n1 \le y_1 \le y_2 \le n, and x1+y1+2x2+y2x_1 + y_1 + 2 \le x_2 + y_2. Don't forget to 'flush', to get the answer.

In response, you will receive 11, if there exists a path going from (x1,y1)(x_1, y_1) to (x2,y2)(x_2, y_2) only to the right or down, numbers in cells of which form a palindrome, and 00 otherwise.

In case your query is invalid or you asked more than n2n^2 queries, program will print 1-1 and will finish interaction. You will receive Wrong answer verdict. Make sure to exit immediately to avoid getting other verdicts.

When you determine numbers in all cells, output "!".

Then output nn lines, the ii-th of which is a string of length nn, corresponding to numbers in the ii-th row of the grid.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see documentation for other languages.

Hack Format

To hack, use the following format.

The first line should contain a single odd integer nn (side of your grid).

The ii-th of nn following lines should contain a string of length nn corresponding to the ii-th row of the grid. Top left element of the grid has to be equal to 11, bottom right has to be equal to 00.

Input

The first line contains odd integer (3n<503 \le n < 50) — the side of the grid.

Samples

输入数据 1

3
0
1
0
1
1
1
1

输出数据 1

? 1 1 1 3
? 1 1 2 3
? 2 1 2 3
? 3 1 3 3
? 2 2 3 3
? 1 2 3 2
? 1 2 3 3
!
100
001
000