The KAIST School Idol Club is a school idol club that enjoys immense global popularity. The $N=2^k$ members belonging to the KAIST School Idol Club plan to visit the famous premium ice cream brand RUN (Rapid Unit-freeze Nitrogen) to eat ice cream.

Due to severe financial difficulties, RUN could only provide a single long ice cream of length $L=2^{10}$ meters. This ice cream consists of different flavors for each $1$ meter segment.

In order to ensure that all members of the School Idol Club can enjoy the ice cream with sufficient satisfaction, the manager Jeonghyeon Jeon plans to divide the ice cream into $N$ pieces and distribute them to the members.

Since each member has different tastes, even the same flavor of ice cream may give different levels of satisfaction to different members. The taste of the $i$-th member can be represented by integers $a_{i,1},a_{i,2}, \cdots, a_{i,L}$ between $1$ and $9$, which are "unknown to Jeonghyeon Jeon."

The satisfaction felt by the $i$-th member after eating all the ice cream in the interval $[x,y]$ is given by $$ ((\sum_{j=1}^{\lfloor y\rfloor}2^{a_{i,j}})+2^{a_{i,\lfloor y\rfloor +1}}\times(y-\lfloor y\rfloor))-((\sum_{j=1}^{\lfloor x\rfloor}2^{a_{i,j}})+2^{a_{i,\lfloor x\rfloor+1}}\times(x-\lfloor x\rfloor)) $$

For example, if the $i$-th member eats all the ice cream in the interval $[j-1,j]$, the satisfaction obtained is $2^{a_{i,j}}$, and if the $i$-th member eats all the ice cream, the total satisfaction is $T_i=\sum_{j=1}^{L} 2^{a_{i,j}}$.

Jeonghyeon Jeon wants the satisfaction obtained by each member to be as equal as possible. Therefore, Jeonghyeon Jeon wants to find a permutation $P_1,P_2,\cdots,P_N$ and integers $x_0=0<x_1<\cdots<x_{N-1}<x_N=L\times 2^{30}$ such that the satisfaction obtained by member $P_i$ after eating all the ice cream in the interval $[\frac{x_{i-1}}{2^{30}}, \frac{x_{i}}{2^{30}}]$ is at least $\frac{T_{P_i}}{N}-\frac{1}{2^{20}}$.

However, it is impossible to perform such a partition without knowing the members' tastes. Therefore, Jeonghyeon Jeon can ask each member one of the following two types of queries, at most $30,000$ times in total.

• ? 0 i x y: Let $r$ be the satisfaction obtained by the $i$-th member after eating all the ice cream in the interval $[\frac{x}{2^{30}},\frac{y}{2^{30}}]$. Output $2^{30}\times r$ ($1\le i\le N, 0\le x\le y\le L\times 2^{30}$).
• ? 1 i x r: Output a value $y$ such that the satisfaction obtained by the $i$-th member after eating all the ice cream in the interval $[\frac{x}{2^{30}},\frac{y}{2^{40}}]$ is exactly $\frac{r}{2^{30}}$ ($1\le i\le N, 0\le x\le L\times 2^{30}, 0\le r\le 2^{50}$). If no such $y$ exists, output $-1$. If such a $y$ exists, it can be proven that $y$ is always an integer.

You are another manager of the KAIST School Idol Club. Help Jeonghyeon Jeon by providing any partition that satisfies the above conditions. It can be proven that at least one such partition always exists.

Constraints

• $1\le k\le 10$

Subtasks

1. (6 points) $k=1$

2. (9 points) For all $1\le i\le 2^k, 1\le j\le L$, $a_{i,j}=1$

3. (15 points) For all $1\le i<2^k, 1\le j\le L$, $a_{i,j}=a_{i+1,j}$

4. (28 points) $k\le 5$

5. (42 points) No additional constraints.

Interaction

Initially, the grader provides a positive integer $k$ to the program.

After that, the program can receive answers to at most $30,000$ queries of the following two types.

• ? 0 i x y: Let $r$ be the satisfaction obtained by the $i$-th member after eating all the ice cream in the interval $[\frac{x}{2^{30}},\frac{y}{2^{30}}]$. Output $2^{30}\times r$ ($1\le i\le N, 0\le x,y\le L\times 2^{30}$).
• ? 1 i x r: Output a value $y$ such that the satisfaction obtained by the $i$-th member after eating all the ice cream in the interval $[\frac{x}{2^{30}},\frac{y}{2^{40}}]$ is exactly $\frac{r}{2^{30}}$ ($1\le i\le N, 0\le x\le L\times 2^{30}, 0\le r\le 2^{50}$). If no such $y$ exists, output $-1$. If such a $y$ exists, it can be proven that $y$ is always an integer.

If the program finds a partition satisfying all conditions, it should output the answer in the following format.

• ! $P_1$ $P_2$ $\cdots$ $P_N$ $x_1$ $x_2$ $\cdots$ $x_{N-1}$

After each output, the buffer must be flushed.

Example

Example 1

Input

1

3298534883328

3298534883328

2199023255552

1099511627776

Output

? 0 1 0 1099511627776

? 0 2 0 1099511627776

? 0 1 0 549755813888

? 0 2 0 549755813888

! 1 2 549755813888

Explanation

In this example, for $1\le j\le 512$, $a_{1,j}=2, a_{2,j}=1$, and for $513\le j\le 1024$, $a_{1,j}=1, a_{2,j}=2$.

For your first query, you asked for the satisfaction obtained by member $1$ after eating all the ice cream in the interval $[0,\frac{1099511627776}{2^{30}}]=[0,1024]$, and from the interactor's response, you found that the satisfaction is $\frac{3298534883328}{2^{30}}=3072$.

For your second query, you asked for the satisfaction obtained by member $2$ after eating all the ice cream in the interval $[0,\frac{1099511627776}{2^{30}}]=[0,1024]$, and from the interactor's response, you found that the satisfaction is $\frac{3298534883328}{2^{30}}=3072$.

For your third query, you asked for the satisfaction obtained by member $1$ after eating all the ice cream in the interval $[0,\frac{549755813888}{2^{30}}]=[0,512]$, and from the interactor's response, you found that the satisfaction is $\frac{2199023255552}{2^{30}}=2048$.

For your fourth query, you asked for the satisfaction obtained by member $2$ after eating all the ice cream in the interval $[0,\frac{549755813888}{2^{30}}]=[0,512]$, and from the interactor's response, you found that the satisfaction is $\frac{1099511627776}{2^{30}}=1024$.

Based on the queries so far, you determined that the condition is satisfied if member $1$ eats the ice cream in the interval $[0,512]$ and member $2$ eats the ice cream in the interval $[512,1024]$, and you output this using the correct query format.

Notes

You can flush the output buffer by using the following methods:

• C: fflush(stdout);
• C++: std::cout << std::flush;
• Java: System.out.flush();
• Python: sys.stdout.flush()

For other languages, you should refer to the language-specific specifications.

You can use the sample grader as attached.