KUPC-kun은 다음 문제를 해결하는 프로그램을 작성했습니다. $N$개의 정점을 가진 트리 $T = (V, E)$가 주어집니다. 길이가 $k$인 $T$의 정점 수열 $\{a_1, \dots, a_k\}$에 대해, 그 점수를 다음과 같이 정의합니다.

• $d(u, v)$를 $T$에서 정점 $u$와 $v$ 사이의 경로에 있는 간선의 개수라고 합시다. 그러면 점수는 $\prod_{i=1}^{k} d(a_i, a_{(i \bmod k)+1)}$입니다.

$V$의 부분집합 $S$가 주어집니다. 각 $1 \le k \le N$에 대하여 다음 값 $q_k$를 구하십시오.

• 요소가 $S$에 속하는 모든 길이 $k$인 정점 수열 $\{a_1, \dots, a_k\}$에 대한 점수의 합을 $2^{61} - 1$로 나눈 나머지.

KUPC-kun은 트리 $T$에 대한 정보를 미리 비밀리에 보관하고 있으며, 프로그램에 주어진 트리로서 $T$를 계속 사용합니다. 여러분은 위 프로그램을 사용하여 트리의 잎(leaf)에 대한 정보를 복구하려고 합니다. 트리의 정점 개수를 $N$이라 할 때, 다음 질문을 최대 $N$번 할 수 있습니다.

• $V$의 부분집합 $S$를 선택하여 프로그램의 출력을 요청합니다.

KUPC-kun의 프로그램이 올바르다고 가정하고, 질문을 통해 얻은 정보로부터 트리 $T$에 포함된 모든 잎을 식별하십시오. 판정기는 적응형(adaptive)이 아니며, 인터랙션이 시작되기 전에 트리 $T$는 고정되어 있습니다.

인터랙션 프로토콜

먼저, 표준 입력으로 $N$이 주어집니다. ($2 \le N \le 50$) 각 질문에 대해, 표준 출력으로 다음 형식에 맞춰 출력하십시오.

? $s_1s_2 \dots s_N$

여기서 $s_1s_2 \dots s_N$은 부분집합 $S$를 나타내는 길이 $N$의 문자열이며, $i \in S$이면 $s_i = 1$이고 $i \notin S$이면 $s_i = 0$입니다. 그에 대한 응답으로 표준 입력으로부터 다음이 주어집니다.

$q_1 \ q_2 \ \dots \ q_N$

모든 잎을 식별했다면, 다음 형식으로 답을 출력하십시오.

! $t_1t_2 \dots t_N$

여기서 $t_1t_2 \dots t_N$은 길이 $N$의 문자열이며, $i$가 잎이면 $t_i = 1$이고 잎이 아니면 $t_i = 0$입니다. 이 출력을 한 후, 즉시 프로그램을 종료하십시오. 무언가를 출력할 때마다 끝에 줄바꿈을 추가하고 표준 출력을 플러시(flush)하십시오.

예제

입력 1

5
0 8 0 32 0
0 44 108 968 3960
0 0 0 0 0
0 76 348 3336 22200

출력 1

? 00101
? 11001
? 10000
? 11111
! 11001

참고

첫 번째 예제에서 판정기가 비밀리에 유지하는 트리의 간선 집합은 $(1, 3), (2, 3), (3, 4), (4, 5)$입니다. 첫 번째 질문에서 $S = \{3, 5\}$입니다. $d(3, 3) = 0, d(3, 5) = d(5, 3) = 2, d(5, 5) = 0$임에 유의하십시오. 예를 들어, 요소가 $S$에 속하는 길이 2인 정점 수열 $a$는 다음과 같이 4가지가 있습니다.

• $a = (3, 3)$인 경우, 이 수열의 점수는 $d(3, 3) \times d(3, 3) = 0 \times 0 = 0$입니다.
• $a = (3, 5)$인 경우, 이 수열의 점수는 $d(3, 5) \times d(5, 3) = 2 \times 2 = 4$입니다.
• $a = (5, 3)$인 경우, 이 수열의 점수는 $d(5, 3) \times d(3, 5) = 2 \times 2 = 4$입니다.
• $a = (5, 5)$인 경우, 이 수열의 점수는 $d(5, 5) \times d(5, 5) = 0 \times 0 = 0$입니다.

판정기는 $q_2$에 대해 $0 + 4 + 4 + 0$을 $2^{61} - 1$로 나눈 나머지인 8을 응답합니다. 다른 수열 길이에 대해서도 유사하게 계산하면 판정기의 응답인 $0 \ 8 \ 0 \ 32 \ 0$을 얻을 수 있습니다. 이 트리의 잎은 정점 $1, 2, 5$이며, $! \ 11001$을 출력하면 잎 식별이 올바르게 완료됩니다.