هذه مسألة تفاعلية.

كتب 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$.

على سبيل المثال، توجد متتاليات الرؤوس الـ $4$ التالية $a$ ذات الطول $2$ والتي تنتمي عناصرها إلى $S$.

• إذا كان $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 تكمل تحديد الأوراق بشكل صحيح.