โจทย์ข้อนี้เป็นแบบโต้ตอบ (interactive) หลังจากพิมพ์แต่ละบรรทัด คุณต้องล้างบัฟเฟอร์เอาต์พุต (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$ คือผลลัพธ์ bitwise xor ของสมาชิกตัวที่ $i$ ของ $A$ และ $B$ เราเขียนแทน xor ด้วย $\oplus$
• สร้างเซต $S$ ให้เป็นเซตของค่าทั้งหมดที่สามารถหาได้จากการนำสับเซตของสมาชิกบางส่วนของ $C$ มา xor กัน โดยเฉพาะอย่างยิ่ง สำหรับสับเซตว่าง ค่า 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$

ผลลัพธ์ bitwise xor ของตัวเลขสองตัว $x$ และ $y$ จะมีบิตที่ $i$ เป็น $1$ ก็ต่อเมื่อมีเพียงตัวใดตัวหนึ่งระหว่าง $x$ และ $y$ เท่านั้นที่มีบิตที่ $i$ เป็น $1$ ตัวอย่างเช่น $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

ตัวตรวจตัวอย่างไม่รับประกันว่าจะทำงานเหมือนกับตัวตรวจอย่างเป็นทางการทุกประการ อย่างไรก็ตาม ทั้งสองตัวไม่ได้เป็นแบบปรับเปลี่ยนตามคำถาม (adaptive)