זוהי בעיה אינטראקטיבית. המגבלה היא $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 המורכבת מאפסים ומאחדים. לאחר פקודה זו תוכנית המשתתף צריכה להסתיים מיד.

דוגמאות

קלט 1

2
3
3
1
3

פלט 1

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

הערה

הדוגמה שלעיל ניתנת רק כדי להדגים את הפורמט. בדוגמה זו אורך המחרוזת הוא 5. בבדיקה האמיתית הראשונה, כמו בכל שאר הבדיקות, אורך המחרוזת שיש לנחש הוא בדיוק 1000.