KUPC-kun đã viết một chương trình giải quyết bài toán sau đây: Cho một cây $T = (V, E)$ với $N$ đỉnh. Với một dãy $\{a_1, \dots, a_k\}$ gồm các đỉnh của $T$ có độ dài $k$, định nghĩa điểm số của nó như sau: - Gọi $d(u, v)$ là số lượng cạnh trên đường đi giữa hai đỉnh $u$ và $v$ trong $T$. Khi đó, điểm số là $\prod_{i=1}^{k} d(a_i, a_{(i \pmod k)+1})$.

Cho trước một tập con $S$ của $V$. Với mỗi $1 \le k \le N$, hãy tìm giá trị $q_k$ sau đây: - Tổng các điểm số của tất cả các dãy đỉnh $\{a_1, \dots, a_k\}$ có độ dài $k$ mà các phần tử của chúng đều thuộc $S$, lấy theo modulo $2^{61} - 1$.

KUPC-kun giữ bí mật thông tin về cây $T$ từ trước và tiếp tục sử dụng $T$ làm cây được cung cấp cho chương trình. Bạn đang cố gắng khôi phục thông tin về các lá của cây bằng cách sử dụng chương trình trên. Gọi $N$ là số đỉnh của cây, bạn có thể đặt câu hỏi sau đây tối đa $N$ lần:

• Chọn một tập con $S$ của $V$ và yêu cầu chương trình trả về kết quả.

Giả sử chương trình của KUPC-kun là đúng, hãy xác định tất cả các lá có trong cây $T$ từ thông tin thu được qua các câu hỏi. Giám khảo không thích nghi (non-adaptive), và cây $T$ được cố định trước khi quá trình tương tác bắt đầu.

Giao tiếp

Đầu tiên, $N$ được cung cấp từ đầu vào tiêu chuẩn. ($2 \le N \le 50$) Với mỗi câu hỏi, hãy xuất ra đầu ra tiêu chuẩn theo định dạng sau: ? $s_1s_2 \dots s_N$

Ở đây, $s_1s_2 \dots s_N$ là một chuỗi có độ dài $N$ biểu diễn tập con $S$, trong đó $s_i = 1$ nếu $i \in S$, và $s_i = 0$ nếu $i \notin S$. Để phản hồi, giá trị sau đây được cung cấp từ đầu vào tiêu chuẩn: $q_1 \ q_2 \ \dots \ q_N$

Sau khi đã xác định được tất cả các lá, hãy xuất câu trả lời của bạn theo định dạng sau: ! $t_1t_2 \dots t_N$

Ở đây, $t_1t_2 \dots t_N$ là một chuỗi có độ dài $N$, trong đó $t_i = 1$ nếu $i$ là một lá, và $t_i = 0$ nếu nó không phải là lá. Sau khi xuất kết quả này, hãy kết thúc chương trình của bạn ngay lập tức. Bất cứ khi nào bạn xuất ra một cái gì đó, hãy thêm một ký tự xuống dòng ở cuối và xóa bộ đệm đầu ra tiêu chuẩn (flush).

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

? 00101
? 11001
? 10000
? 11111
! 11001

Ghi chú

Đối với ví dụ đầu tiên, tập cạnh của cây mà giám khảo giữ bí mật là $(1, 3), (2, 3), (3, 4), (4, 5)$. Trong câu hỏi đầu tiên, $S = \{3, 5\}$. Lưu ý rằng $d(3, 3) = 0, d(3, 5) = d(5, 3) = 2, d(5, 5) = 0$. Ví dụ, có 4 dãy đỉnh $a$ độ dài 2 mà các phần tử thuộc $S$:

• Nếu $a = (3, 3)$, thì điểm số của dãy này là $d(3, 3) \times d(3, 3) = 0 \times 0 = 0$
• Nếu $a = (3, 5)$, thì điểm số của dãy này là $d(3, 5) \times d(5, 3) = 2 \times 2 = 4$
• Nếu $a = (5, 3)$, thì điểm số của dãy này là $d(5, 3) \times d(3, 5) = 2 \times 2 = 4$
• Nếu $a = (5, 5)$, thì điểm số của dãy này là $d(5, 5) \times d(5, 5) = 0 \times 0 = 0$

Giám khảo phản hồi 8 cho $q_2$, là phần dư khi $0 + 4 + 4 + 0$ chia cho $2^{61} - 1$. Bằng cách tính toán tương tự cho các độ dài dãy khác, chúng ta nhận được phản hồi của giám khảo là 0 8 0 32 0. Các lá của cây này là các đỉnh 1, 2, 5, và việc xuất ra ! 11001 hoàn thành chính xác việc xác định các lá.