זוהי בעיה אינטראקטיבית.

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$ מתוך המידע שהתקבל באמצעות השאלות.

השופט אינו אדפטיבי, והעץ $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 משלימה בהצלחה את זיהוי העלים.