นี่คือโจทย์แบบโต้ตอบ (interactive problem)

KUPC-kun เขียนโปรแกรมสำหรับแก้โจทย์ปัญหาต่อไปนี้

กำหนดต้นไม้ $T = (V, E)$ ที่มี $N$ จุดยอด สำหรับลำดับ $\{a_1, \dots, a_k\}$ ของจุดยอดของ $T$ ที่มีความยาว $k$ นิยามคะแนนของมันดังต่อไปนี้ - ให้ $d(u, v)$ เป็นจำนวนเส้นเชื่อมบนเส้นทางระหว่างจุดยอด $u$ และ $v$ ใน $T$ แล้วคะแนนคือ $\prod_{i=1}^k d(a_i, a_{(i \bmod k)+1})$

กำหนดสับเซต $S$ ของ $V$ มาให้ สำหรับแต่ละ $1 \le k \le N$ จงหาค่า $q_k$ ต่อไปนี้ - ผลรวมของคะแนนของทุกลำดับจุดยอด $\{a_1, \dots, a_k\}$ ที่มีความยาว $k$ ซึ่งสมาชิกทั้งหมดอยู่ใน $S$ มอดุโล $2^{61} - 1$

KUPC-kun เก็บข้อมูลของต้นไม้ $T$ ไว้เป็นความลับล่วงหน้า และยังคงใช้ $T$ เป็นต้นไม้ที่ป้อนให้กับโปรแกรมต่อไป

คุณกำลังพยายามกู้คืนข้อมูลของจุดยอดใบโดยใช้โปรแกรมข้างต้น เมื่อให้จำนวนจุดยอดของต้นไม้เป็น $N$ คุณสามารถถามคำถามต่อไปนี้ได้ไม่เกิน $N$ ครั้ง

• เลือกสับเซต $S$ ของ $V$ และถามหาผลลัพธ์ของโปรแกรม

สมมติว่าโปรแกรมของ KUPC-kun ถูกต้อง จงระบุจุดยอดใบทั้งหมดที่อยู่ในต้นไม้ $T$ จากข้อมูลที่ได้ผ่านการถามคำถาม

ระบบตรวจไม่ปรับเปลี่ยนข้อมูลตามคำถาม (not adaptive) และต้นไม้ $T$ ถูกกำหนดตายตัวไว้ก่อนที่การโต้ตอบจะเริ่มต้นขึ้น

รูปแบบการโต้ตอบ

ขั้นแรก รับค่า $N$ จากข้อมูลนำเข้ามาตรฐาน ($2 \le N \le 50$)

สำหรับแต่ละคำถาม ให้พิมพ์ออกทางข้อมูลส่งออกมาตรฐานในรูปแบบต่อไปนี้

? s1s2...sN

ในที่นี้ $s_1s_2\cdots s_N$ คือสตริงความยาว $N$ ที่แทนสับเซต $S$ โดยที่ $s_i = 1$ ถ้า $i \in S$ และ $s_i = 0$ ถ้า $i \notin S$

สำหรับการตอบกลับ ข้อมูลต่อไปนี้จะถูกส่งมาจากข้อมูลนำเข้ามาตรฐาน

q1 q2 ... qN

เมื่อคุณระบุจุดยอดใบทั้งหมดได้แล้ว ให้แสดงคำตอบของคุณในรูปแบบต่อไปนี้

! t1t2...tN

ในที่นี้ $t_1t_2\cdots t_N$ คือสตริงความยาว $N$ โดยที่ $t_i = 1$ ถ้า $i$ เป็นจุดยอดใบ และ $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$

ตัวอย่างเช่น มีลำดับจุดยอด $a$ ความยาว $2$ ที่สมาชิกอยู่ใน $S$ ทั้งหมด $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$

ระบบตรวจจึงตอบกลับมาเป็น $8$ สำหรับค่า $q_2$ ซึ่งเป็นเศษเหลือเมื่อนำ $0 + 4 + 4 + 0$ ไปหารด้วย $2^{61} - 1$

เมื่อคำนวณในทำนองเดียวกันสำหรับความยาวลำดับอื่นๆ เราจะได้คำตอบของระบบตรวจเป็น 0 8 0 32 0

จุดยอดใบของต้นไม้นี้คือจุดยอด $1, 2, 5$ และการแสดงผล ! 11001 เป็นการระบุจุดยอดใบได้อย่างถูกต้อง