โจทย์นี้เป็นโจทย์แบบโต้ตอบ จำกัดจำนวนคำถามไว้ที่ $18\,000$ ครั้ง

กรรมการมีสตริงลับที่ประกอบด้วยเลขฐานสองจำนวน 1000 ตัวพอดี ในแต่ละกรณีทดสอบ สตริงจะถูกกำหนดไว้ล่วงหน้าและไม่เปลี่ยนแปลง คุณต้องหาสตริงนี้โดยใช้คำถาม

ในแต่ละคำถาม คุณเลือกช่วง $[a, b]$ ($1 \le a \le b \le 1000$) ที่ต้องการถาม จากนั้นกรรมการจะโยนเหรียญและให้ค่าหนึ่งในสองค่าต่อไปนี้ โดยแต่ละกรณีมีความน่าจะเป็น 50%:

1. จำนวนเลข 1 ในช่วง $[a, b]$;
2. ค่าตั้งแต่ $0$ ถึง $b - a + 1$ ที่ไม่เท่ากับจำนวนเลข 1 ในช่วงนั้น โดยสุ่มอย่างสม่ำเสมอ

คุณห้ามใช้คำถามเดิมสองครั้ง ค่าสุ่มทั้งหมดที่ใช้ในโจทย์นี้มีการแจกแจงแบบสม่ำเสมอและเป็นอิสระต่อกัน

การโต้ตอบ

โปรแกรมของผู้เข้าแข่งขันต้องโต้ตอบกับโปรแกรมของกรรมการโดยพิมพ์คำสั่งในรูปแบบใดรูปแบบหนึ่งต่อไปนี้:

• ? a b คำถามสำหรับช่วง $[a, b]$ เพื่อตอบคำถามนี้ โปรแกรมของกรรมการจะพิมพ์จำนวนเต็มหนึ่งจำนวน ซึ่งมีโอกาส 50% ที่จะเป็นจำนวนเลข 1 ในช่วง $[a, b]$ มิฉะนั้นจะเป็นค่าสุ่มตั้งแต่ $0$ ถึง $b - a + 1$ ที่ไม่เท่ากับจำนวนนั้น
• ! ans คำตอบของโจทย์ โดย ans เป็นสตริงความยาว 1000 ที่ประกอบด้วย 0 และ 1 หลังคำสั่งนี้ โปรแกรมของผู้เข้าแข่งขันควรหยุดทำงานทันที

ตัวอย่าง

ข้อมูลนำเข้า 1

2
3
3
1
3

ข้อมูลส่งออก 1

? 1 3
? 1 5
? 3 5
? 2 3
? 2 5
! 01101

หมายเหตุ

ตัวอย่างข้างต้นมีไว้เพื่อแสดงรูปแบบเท่านั้น ในตัวอย่างนี้สตริงมีความยาว 5 ในกรณีทดสอบจริงกรณีแรกและกรณีอื่นทั้งหมด สตริงที่ต้องทายมีความยาว 1000 พอดี