هذه المسألة تفاعلية. بعد طباعة كل سطر، يجب عليك تفريغ مخزن الإخراج المؤقت (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$ مفعلاً إذا وفقط إذا كان البت $i$ مفعلاً في واحد فقط بالضبط من $x$ و $y$. على سبيل المثال، $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. لاختبار حلك، قم بترجمته برمجياً (compile)، ثم مرر اسم الاختبار والملف التنفيذي الخاص بك إلى ./grader المترجم:

./grader [test] [executable]

على سبيل المثال: ./grader 0b.in ./abc

لا يُضمن أن يتصرف مصحح المثال بشكل مطابق للمصحح الرسمي. ومع ذلك، فإن كليهما غير تكيفي (non-adaptive).