זוהי בעיה אינטראקטיבית.

ל-Little Cyan Fish יש גרף פשוט לא מכוון ונסתר עם $n$ צמתים, המסומנים מ-$1$ עד $n$. אתם יודעים את הערך של $n$, אך אינכם יודעים אף אחת מהקשתות. Little Cyan Fish אוהב את המושג של חתך (cut). עבור קבוצת צמתים $S$, נסמן ב-$\operatorname{cut}(S)$ את מספר הקשתות שיש להן בדיוק קצה אחד ב-$S$.

Little Cyan Fish מאפשר לכם להשוות חתכים באמצעות ביצוע שאילתות. בשאילתה אחת, אתם בוחרים שתי קבוצות של צמתים $S_1$ ו-$S_2$. Little Cyan Fish אומר לכם האם $\operatorname{cut}(S_1)$ קטן מ-, שווה ל-, או גדול מ-$\operatorname{cut}(S_2)$.

אתם כנראה יכולים לנחש שהמילים הבאות יעסקו בשחזור הגרף, אבל הפעם המשימה קלה יותר. Little Cyan Fish נותן לכם צומת $u$, והוא רוצה שתמצאו את כל הצמתים השכנים ל-$u$ בלכל היותר $n + 10$ שאילתות.

קלט

השורה הראשונה של הקלט מכילה שני מספרים שלמים $n$ ו-$u$ ($1 \le n \le 1000$, $1 \le u \le n$), המציינים את מספר הצמתים ואת הצומת הנתון, בהתאמה. לאחר מכן, האינטראקציה מתחילה.

פרוטוקול אינטראקציה

כדי לבצע שאילתה, הדפיסו שורה בפורמט הבא:

$$?\ s_1\ s_2$$

כאשר $s_1$ ו-$s_2$ הן מחרוזות באורך $n$, המורכבות אך ורק מהתווים 0 ו-1. עבור כל $j \in \{1, 2\}$, הצומת $i$ שייך ל-$S_j$ אם ורק אם התו ה-$i$ של $s_j$ הוא 1. הקבוצות עשויות להיות ריקות, עשויות לחפוף, ועשויות להיות שוות.

כתגובה לשאילתה, תקבלו תו בודד <, =, או >, שמשמעותו היא ש-$\operatorname{cut}(S_1)$ קטן מ-, שווה ל-, או גדול מ-$\operatorname{cut}(S_2)$, בהתאמה. עליכם להבטיח שמספר השאילתות שאתם מבצעים אינו עולה על $n + 10$.

כדי לדווח על התשובה, הדפיסו שורה בפורמט הבא:

$$!\ k\ v_1\ v_2\ \dots\ v_k$$

כאשר $k$ ($0 \le k \le n - 1$) הוא מספר הצמתים השכנים ל-$u$, ו-$v_1, v_2, \ldots, v_k$ הם המספרים המזהים השונים שלהם בכל סדר שהוא. אם $k = 0$, הדפיסו ! 0. דיווח על התשובה אינו נספר כשאילתה. התוכנית שלכם חייבת להסתיים מיד לאחר הדיווח על התשובה.

לאחר הדפסת שאילתה או דיווח על התשובה, אל תשכחו להדפיס תו ירידת שורה ולרוקן את חוצץ הפלט (flush). אם תבצעו שאילתה לא חוקית או תחרגו ממגבלת השאילתות, המאמת (interactor) יסגור את ערוץ הקלט והתוכנית שלכם חייבת להסתיים.

בבעיה זו, המאמת הוא אדפטיבי (adaptive). משמעות הדבר היא שהגרף עשוי להשתנות בהתאם לשאילתות שלכם, כל עוד הוא אינו סותר אף תגובה קודמת. התשובה שלכם חייבת להיות נכונה עבור כל גרף שעולה בקנה אחד עם כל התגובות שקיבלתם.

דוגמאות

קלט 1

4 1

<

=

<

=

פלט 1

? 0000 1000

? 0100 1100

? 0010 1010

? 0001 1001

! 2 2 4

הערה

גרף אחד שעולה בקנה אחד עם האינטראקציה שבדוגמה מכיל את הקשתות $(1, 2)$, $(1, 4)$ ו-$(2, 3)$.

כלי בדיקה: כלי בדיקה מסופק כדי לעזור למתחרים לפתח ולבדוק את הפתרונות שלהם. תוכלו להוריד כלי זה מהקבצים המצורפים. הריצו את הכלי עם האפשרות -h כדי להציג הוראות שימוש. הכלי בודק את האינטראקציה ואת התשובה המדווחת, אך אינו אוכף את מגבלת הזמן או הזיכרון.

כלי הבדיקה משתמש בגרף קבוע המוגדר בקובץ הקלט שלו לאורך כל האינטראקציה, בעוד שהמאמת הרשמי הוא אדפטיבי. מעבר בדיקות באמצעות כלי הבדיקה אינו מבטיח שהפתרון שלכם נכון מול המאמת הרשמי.