카이스트 스쿨 아이돌 동호회는 세계적으로 거대한 인기를 끌고 있는 스쿨 아이돌 동호회이다. 카이스트 스쿨 아이돌 동호회에 소속된 $N=2^k$명의 멤버들은 이번에 유명한 고급 아이스크림 브랜드인 RUN(Rapid Unit-freeze Nitrogen)에 방문하여 아이스크림을 먹고자 한다.

심각한 재정 문제로 인해, RUN에서는 오직 $L=2^{10}$미터의 기다란 아이스크림을 줄 수밖에 없었다. 해당 아이스크림은 $1$미터마다 색다른 맛으로 구성되어있다.

스쿨 아이돌 동호회의 멤버들이 충분한 만족감을 가지고 아이스크림을 먹을 수 있도록 하기 위해서, 매니저인 전정현은 아이스크림을 $N$개의 조각으로 나누어 각 멤버들에게 분배하고자 한다.

각 멤버들의 입맛은 전부 다르기 때문에, 같은 맛의 아이스크림이더라도 각 멤버들은 서로 다른 만족감을 느낄 수 있다. $i$번 멤버의 입맛은 "전정현이 모르는" $1$ 이상 $9$ 이하의 정수 $a_{i,1},a_{i,2}, \cdots, a_{i,L}$들로 표현할 수 있다.

$i$번 멤버가 구간 $[x,y]$에 있는 아이스크림을 전부 먹었을 때 느끼는 만족감은 $((\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))$와 같이 나타난다.

예를 들어 $i$번 멤버가 구간 $[j-1,j]$에 있는 아이스크림을 전부 먹었을 때 느끼는 만족감은 $2^{a_{i,j}}$이며, $i$번 멤버가 모든 아이스크림을 먹을 시 얻는 만족감은 $T_i=\sum_{j=1}^{L} 2^{a_{i,j}}$이다.

전정현은 각 멤버들이 얻는 만족감이 최대한 균등하기를 원한다. 따라서 전정현은 순열 $P_1,P_2,\cdots,P_N$과 정수 $x_0=0<x_1<\cdots<x_{N-1}<x_N=L\times 2^{30}$을 찾아서, $P_i$번 멤버가 구간 $[\frac{x_{i-1}}{2^{30}}, \frac{x_{i}}{2^{30}}]$에 있는 모든 아이스크림을 먹었을 때 느끼는 만족감이 $\frac{T_{P_i}}{N}-\frac{1}{2^{20}}$ 이상이 되도록 하고자 한다.

그러나, 멤버들의 입맛을 모르면서 이러한 분할을 하는 것은 불가능한 일이다. 따라서 전정현은 각 멤버에게 다음의 두 질문 중 하나를, 모든 멤버를 통틀어서 최대 $30,000$번 할 수 있다.

• ? 0 i x y: $i$번 멤버가 구간 $[\frac{x}{2^{30}},\frac{y}{2^{30}}]$에 있는 아이스크림을 전부 먹었을 때 느끼는 만족감이 $r$이라고 할 때, $2^{30}\times r$을 답한다($1\le i\le N, 0\le x\le y\le L\times 2^{30}$).
• ? 1 i x r: $i$번 멤버가 구간 $[\frac{x}{2^{30}},\frac{y}{2^{40}}]$에 있는 아이스크림을 전부 먹었을 때 느끼는 만족감이 정확히 $\frac{r}{2^{30}}$이 되는 수 $y$를 답한다($1\le i\le N, 0\le x\le L\times 2^{30}, 0\le r\le 2^{50}$). 만약 이러한 $y$가 없다면 $-1$로 답한다. 만약 $y$가 존재한다면 그러한 $y$는 항상 정수임을 증명할 수 있다.

당신은 카이스트 스쿨 아이돌 동호회의 또다른 매니저이다. 전정현을 도와 위의 조건을 만족하는 분할을 아무거나 하나 알려주자. 이러한 분할이 적어도 하나 이상 존재함을 증명할 수 있다.

제약 조건

• $1\le k\le 10$

부분문제

1. (6점) $k=1$

2. (9점) 모든 $1\le i\le 2^k, 1\le j\le L$에 대해서 $a_{i,j}=1$

3. (15점) 모든 $1\le i<2^k, 1\le j\le L$에 대해서 $a_{i,j}=a_{i+1,j}$

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

5. (42점) 추가 제약 조건 없음

인터랙션

맨 처음, 그레이더는 양의 정수 $k$를 프로그램에게 제공한다.

이후 프로그램은 최대 $30,000$번 다음과 같은 두 종류의 쿼리에 대한 답을 받을 수 있다.

• ? 0 i x y: $i$번 멤버가 구간 $[\frac{x}{2^{30}},\frac{y}{2^{30}}]$에 있는 아이스크림을 전부 먹었을 때 느끼는 만족감이 $r$이라고 할 때, $2^{30}\times r$을 답한다($1\le i\le N, 0\le x,y\le L\times 2^{30}$).
• ? 1 i x r: $i$번 멤버가 구간 $[\frac{x}{2^{30}},\frac{y}{2^{40}}]$에 있는 아이스크림을 전부 먹었을 때 느끼는 만족감이 정확히 $\frac{r}{2^{30}}$이 되는 수 $y$를 답한다($1\le i\le N, 0\le x\le L\times 2^{30}, 0\le r\le 2^{50}$). 만약 이러한 $y$가 없다면 $-1$로 답한다. 만약 $y$가 존재한다면 그러한 $y$는 항상 정수임을 증명할 수 있다.

프로그램이 모든 조건을 만족하는 분할을 알아냈다면, 다음과 같은 형식으로 답을 출력한다.

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

매 출력 이후에는 버퍼를 비워야 한다.

예제

예제 1

입력

1

3298534883328

3298534883328

2199023255552

1099511627776

출력

? 0 1 0 1099511627776

? 0 2 0 1099511627776

? 0 1 0 549755813888

? 0 2 0 549755813888

! 1 2 549755813888

설명

해당 예제에서, $1\le j\le 512$에 대해 $a_{1,j}=2, a_{2,j}=1$이고, $513\le j\le 1024$에 대해 $a_{1,j}=1, a_{2,j}=2$이다.

당신은 첫 번째 쿼리로 $1$번 멤버가 구간 $[0,\frac{1099511627776}{2^{30}}]=[0,1024]$에 있는 아이스크림을 전부 먹었을 때 느끼는 만족감을 질문했고, 인터랙터의 답변으로부터 해당 만족감이 $\frac{3298534883328}{2^{30}}=3072$임을 알아냈다.

당신은 두 번째 쿼리로 $2$번 멤버가 구간 $[0,\frac{1099511627776}{2^{30}}]=[0,1024]$에 있는 아이스크림을 전부 먹었을 때 느끼는 만족감을 질문했고, 인터랙터의 답변으로부터 해당 만족감이 $\frac{3298534883328}{2^{30}}=3072$임을 알아냈다.

당신은 세 번째 쿼리로 $1$번 멤버가 구간 $[0,\frac{549755813888}{2^{30}}]=[0,512]$에 있는 아이스크림을 전부 먹었을 때 느끼는 만족감을 질문했고, 인터랙터의 답변으로부터 해당 만족감이 $\frac{2199023255552}{2^{30}}=2048$임을 알아냈다.

당신은 네 번째 쿼리로 $2$번 멤버가 구간 $[0,\frac{549755813888}{2^{30}}]=[0,512]$에 있는 아이스크림을 전부 먹었을 때 느끼는 만족감을 질문했고, 인터랙터의 답변으로부터 해당 만족감이 $\frac{1099511627776}{2^{30}}=1024$임을 알아냈다.

지금까지의 쿼리를 바탕으로, 당신은 $1$번 멤버가 구간 $[0,512]$에 있는 아이스크림을 먹고, $2$번 멤버가 구간 $[512,1024]$에 있는 아이스크림을 먹으면 조건을 만족한다는 사실을 알아냈고, 이를 올바른 쿼리 형식을 통해 답하였다.

노트

출력 버퍼를 비우는 방법은 다음과 같다.

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

이외의 언어에 대해서는 언어별 명세를 참고해야 한다.

샘플 그레이더를 첨부파일로 제공하였다.