هذه مسألة تفاعلية. تذكّر تفريغ مخزن الإخراج المؤقت بعد كل طباعة. يمكنك استخدام ما يلي:

• 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 كيفية استخدامها. تنفّذ الأداة بعض سيناريوهات الاختبار فقط وبعض وظائف برنامج التحكيم الحقيقي فقط.