시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 (추가 시간 없음) 256 MB2000.000%

문제

Your goal is to guess a hidden matrix $n \times n$ consisting of zeros and ones, using at most $5 n^2$ queries. In each query you can ask whether a matrix of your choice occurs as a contiguous submatrix of the hidden matrix.

The interactor in this problem is not adaptive, that is, the matrix is fixed before the interaction starts and doesn't change over time.

인터랙션 프로토콜

At the start of interaction your program receives one integer $n$ from the jury's interactor ($1 \le n \le 60$).

To ask a query about an $a \times b$ submatrix, print a line "? $a$ $b$", followed by $a$ lines containing rows of the matrix. Each row has to contains $b$ characters, each "0" or "1", without spaces. The jury's interactor will reply with a line "1" if your matrix occurs as a contiguous submatrix of a hidden matrix, or with a line "0" otherwise.

If the number of ?-queries exceeds $5n^2$, the jury's interactor prints a line "-1" instead of answering the last ?-query. In that case, your program should terminate immediately, otherwise the judging verdict will be undefined.

To end the interaction, your program has to print a line "!", followed by $n$ lines containing rows of the hidden matrix, in the same format as above. After this, your program should terminate immediately.

예제 입력 1

2


1


1


1


0


1



0



1



예제 출력 1


? 1 1
0

? 1 2
00

? 1 1
1

? 1 2
01

? 1 2
11

? 2 2
00
11

? 2 2
11
00

! 2 2
11
00

노트

Extra line breaks in the sample are given to illustrate the order of interaction, and should not be present in your output, nor would be present in interactor's output.

채점 및 기타 정보

  • 예제는 채점하지 않는다.