משימה זו היא אינטראקטיבית. לאחר הדפסת כל שורה, עליך לרוקן את חוצץ הפלט (flush). ניתן להשתמש ב-cout << flush ב-C++, ב-System.out.flush() ב-Java, וב-sys.stdout.flush() ב-Python. עליך לעקוב בקפדנות אחר ההוראות בסעיף האינטראקציה; אחרת אתה עלול לקבל פסקי דין כמו תשובה שגויה (wrong answer), חריגה ממגבלת הזמן (time limit exceeded) או אחרים.

מכיוון שבכל המשימות הדמויות הראשיות הן גמדים מיתולוגיים, אולי כדאי סוף סוף לחשוב על משהו מוחשי.

קיימת סדרה נסתרת $A$ באורך $N$ המורכבת ממספרים שלמים בטווח $[0, 2^N - 1]$. משימתך היא לשחזר אותה באמצעות מספר מוגבל של שאילתות. בכל שאילתה, אתה מספק סדרה $B$ באורך $N$ עם איברים בטווח $[0, 2^N - 1]$. התגובה מחושבת באופן הבא:

• נוצרת סדרה $C$ שבה האיבר ה-$i$ של $C$ הוא ה-xor הסיביתי (bitwise xor) של האיברים ה-$i$ של $A$ ו-$B$. אנו מסמנים xor באמצעות $\oplus$.
• הקבוצה $S$ נבנית כקבוצת כל הערכים שניתן לקבל על ידי הפעלת xor על תת-קבוצה כלשהי של איברי $C$. בפרט, עבור תת-הקבוצה הריקה, ה-xor הוא $0$.
• התשובה לשאילתה היא $|S|$.

לדוגמה, אם $A = (1, 4, 3)$ ו-$B = (0, 4, 7)$, אז $C = (1 \oplus 0, 4 \oplus 4, 3 \oplus 7) = (1, 0, 4)$ ו-$S = \{0, 1, 4, 5\}$, ולכן התשובה היא $4$.

ב-xor הסיביתי של שני מספרים $x$ ו-$y$, הסיבית ה-$i$ דלוקה אם ורק אם בדיוק לאחד מבין $x$ ו-$y$ יש סיבית $i$ דלוקה. לדוגמה, $5 \oplus 3 = (101)_2 \oplus (011)_2 = (110)_2 = 6$. ב-C++ וב-Python, אופרטור ה-xor הוא ^.

אינטראקציה

הסדרה $A$ קבועה מראש ואינה תלויה בשאילתות המבוצעות.

תחילה, קרא שורה המכילה מספר שלם אחד $1 \le N \le 60$. לאחר מכן תוכל לשאול שאילתות.

כדי לשאול שאילתה, הדפס שורה המכילה ? ואחריו $N$ מספרים שלמים בטווח $[0, 2^N - 1]$. בתגובה, קרא מספר שלם אחד שהוא התשובה.

כאשר תהיה מוכן, הדפס ! ואחריו $N$ המספרים השלמים של הסדרה הנסתרת. לאחר מכן התוכנית שלך צריכה להסתיים ללא פלט נוסף.

זכור לרוקן את הפלט (flush) לאחר כל שאילתה ולאחר כתיבת התשובה. שים רווחים בין מספרים לבין הסימנים ?, !.

דוגמאות

קלט 1

3
4
8

פלט 1

? 1 2 3
? 0 0 0
! 1 3 4

הערה

ההסבר לאינטראקציה שבדוגמה: $N = 3$ שאילתה ? 1 2 3: $B = (1, 2, 3)$, $C = (1 \oplus 1, 3 \oplus 2, 4 \oplus 3) = (0, 1, 7)$, $S = \{0, 1, 6, 7\}$, התשובה היא $4$. שאילתה ? 0 0 0: $B = (0, 0, 0)$, $C = (1 \oplus 0, 3 \oplus 0, 4 \oplus 0) = (1, 3, 4)$, $S = \{0, 1, \dots, 7\}$, התשובה היא $8$. פלט ! 1 3 4: הסדרה הנסתרת היא $A = (1, 3, 4)$.

בדיקה מקומית

בסעיף Files תוכל למצוא את B.zip המכיל מבחני דוגמה ובודק grader.cpp. כדי לבדוק את הפתרון שלך, קמפל אותו, ולאחר מכן העבר את שם המבחן ואת קובץ ההרצה שלך אל ה-./grader המקומפל:

./grader [test] [executable]

לדוגמה: ./grader 0b.in ./abc

לא מובטח שהבודק לדוגמה יתנהג באופן זהה לבודק הרשמי. עם זאת, אף אחד מהם אינו אדפטיבי.