هذه مسألة تفاعلية. الحد الأقصى هو $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 بالضبط.