A graph with exactly 100 vertices, labeled from 1 to 100, is hidden from you. Your goal is to reconstruct this graph using a specific number of queries. One query consists of choosing three distinct vertices of the graph, and the response to the query is the number of edges in the graph that connect any two of the three chosen vertices. Thus, the response to a query is one of the numbers 0, 1, 2, or 3.
The edges in the graph are undirected and have no weights. Therefore, reconstructing the graph means determining whether each pair of vertices is connected.
Interaction
This is an interactive task. Your program must establish a dialogue with the program created by the organizers, which responds to the submitted queries.
Your program can send queries by writing to standard output. Each query should be printed on a separate line and take the form "? a b c", where $a$, $b$, and $c$ are distinct natural numbers such that $1 \le a, b, c \le 100$. The numbers $a$, $b$, and $c$ represent the labels of the chosen vertices in the query.
After each printed query, your program must flush the output and read the response to the query from standard input – a number from the set $\{0, 1, 2, 3\}$ which represents the number of edges among the chosen vertices.
Your program may send at most 161 700 such queries.
When your program has reconstructed the graph, it should print the character ! on a separate line to standard output, and then print the adjacency matrix of the hidden graph. In other words, it is necessary to print 100 lines, each containing 100 characters, either 0 or 1. The number in the $i$-th row and $j$-th column must be 1 if and only if vertices $i$ and $j$ are connected. The printed matrix must be symmetric and contain zeros on the diagonal.
After that, your program must again flush the output and terminate execution.
Subtasks
Let $Q$ be the number of queries your program has made.
If $Q > 161 700$, your program will receive 0 points.
Otherwise, the number of points your program will earn is calculated based on the following table:
| Range | Points |
|---|---|
| $9900 \le Q \le 161 700$ | $10 + 10 \cdot \frac{161700-Q}{161700-9900}$ |
| $4950 \le Q \le 9900$ | $20 + 10 \cdot \frac{9900-Q}{9900-4950}$ |
| $3400 \le Q \le 4950$ | $30 + 70 \cdot \frac{4950-Q}{4950-3400}$ |
| $Q \le 3400$ | $100$ |
Examples
Input 1
? 1 2 3 0 ? 1 2 4 2 ? 1 3 4 2 ! 0001 0001 0001 1110
Output 1
Note
Although the number of vertices in the task will always be 100, for the sake of illustration, we provide an example of an interaction where the number of vertices is 4.