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

• fflush(stdout) או cout.flush() ב-C/C++;
• System.out.flush() ב-Java וב-Kotlin;
• sys.stdout.flush() ב-Python;
• בשפות אחרות, עיינו בתיעוד.

ל-Little Cyan Fish יש תמורה סודית $p_0,p_1,\ldots,p_n$ באורך $n+1$, המורכבת מהמספרים השלמים מ-$0$ עד $n$. הוא רוצה שתנחשו את התמורה הסודית. לשם כך, Little Cyan Fish מאפשר לכם לבצע לכל היותר $1024$ שאילתות בצורה הבאה:

• ? i j: קבלו את האינדקס $k$ ($0\le k\le n$) שעבורו $p_k=|p_i-p_j|$.

כמובן, כדי לבצע שאילתה תקינה, עליכם להבטיח ש-$i$ ו-$j$ הם שני מספרים שלמים בתחום $[0,n]$. לדוגמה, אם $p_0=2,p_1=0,p_2=1$, השאילתה ? 0 2 תחזיר את האינדקס $2$, שכן $|p_0-p_2|=|2-1|=1=p_2$.

Little Cyan Fish רוצה שתמצאו אסטרטגיה לגילוי התמורה. כמובן, הוא אינו רוצה שתנצחו במשחק בקלות רבה מדי. לכן הוא ישנה את התמורה $p$ באופן מסתגל כדי להכשיל אתכם (ראו פרטים נוספים בסעיף ״אינטראקציה״).

קלט

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

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

אינטראקציה

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

$$?\ i\ j$$

כאן $i$ ו-$j$ הם שני מספרים שלמים מ-$0$ עד $n$. עליכם להבטיח שמספר השאילתות אינו עולה על $1024$. בתשובה לשאילתה תקבלו מספר שלם $k$ שעבורו $p_k=|p_i-p_j|$.

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

$$!\ p_0\ p_1\ \ldots\ p_n$$

כאן $p$ היא התמורה שברצונכם לדווח עליה.

לאחר הדפסת שאילתה או דיווח על התשובה, אל תשכחו להדפיס תו שורה חדשה ולרוקן את זרם הפלט.

בבעיה זו, האינטראקטור הוא מסתגל. כלומר, התמורה $p$ עשויה להשתנות בהתאם לשאילתותיכם, כל עוד היא אינה סותרת את השאילתות הקודמות ששאלתם.

דוגמאות

דוגמת אינטראקציה 1

קריאה:

1
3

כתיבה:

? 2 2

קריאה:

1

כתיבה:

? 0 3

קריאה:

3

כתיבה:

! 2 0 3 1

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