題目背景

粉色奶龍和啥龍在van遊戲

題目

啥龍面前有 $N$ 個倉庫取貨口，從左到右編號為 $0$ 到 $N-1$ ，每個取貨口可以指定輸出兩種礦物之一： 源礦 或 藍鐵礦。取貨口連接著一個輸送帶系統，會把出貨口的輸出按照一定順序打亂並傳送到 $N$ 個輸出口，但是啥龍並不知道這個順序。輸出口從左到右編號為 $0$ 到 $N-1$，每個輸出口前有一個速凍仔。

粉色奶龍會讓速凍仔從左到右報數，報數規則如下：

• 最左邊的速凍仔報 $0$
• 對於其他速凍仔，如果自己面前的礦物與左邊相鄰的速凍仔面前的礦物不同，則報左邊速凍仔的報數加 $1$；否則報與左邊相同的數。

然後粉色奶龍會告訴啥龍最後一個速凍仔報了什麼數。

啥龍可以多次進行實驗：每次她可以自由設定所有輸入口的礦物種類，然後得到最後一個速凍仔的報數。她的目標是確定兩個端點輸出口（輸出口 $0$ 和輸出口 $N-1$）對應哪兩個取貨口。

由於啥龍的智商超群，所以請來了管理員你來狐假虎威幫助她贏得遊戲。

交互方式

• 你的程式應首先讀取一行包含整數 $N$：倉庫取貨口的數量。
• 然後，你的程式應與互動器互動。要開始一次實驗，你應輸出一行以問號 ? 開頭，然後是一個長度為 $N$ 的字串，由 $0$ （原礦）和 $1$ （藍鐵礦）組成，表示你如何設定 $N$ 個取貨口的輸出。然後，你的程式應讀取一個整數 $l$ $(0 \leq l < N)$，即最後一個速凍仔報的數。
• 當你想要回答時，輸出一行以驚嘆號 ! 開頭，後面跟著兩個整數 $A$ 和 $B$ $(0\leq A,B < N)$。為了讓你的答案被接受，這必須是對應輸出口 $0$ 和輸出口 $N-1$ 的取貨口編號，順序不限。之後，你的程式應退出。

互動器是非自適應的，這意味著取貨口和輸出口的對應關係在互動開始前就已確定。

請確保在每次實驗後刷新標準輸出，否則你的程式可能會被判定為超時。在 Python 中，只要使用 input() 讀取行，輸出會自動刷新。在 C++ 中，cout << endl; 除了輸出換行外還會刷新；如果使用 printf，請使用 fflush(stdout)。

範例 1

隱藏的對應關係：

在範例 1 中，有 $5$ 個取貨口。 第一次實驗中，速凍仔（從左到右）面前的礦物分別是 源礦、源礦、藍鐵礦、源礦、藍鐵礦，報的數為 $[0, 0, 1, 2, 3]$，所以互動器輸出 $3$。 第二次實驗中，速凍仔（從左到右）面前的礦物分別是 藍鐵礦、源礦、藍鐵礦、藍鐵礦、源礦，報的數為 $[0, 1, 2, 2, 3]$，所以互動器輸出 $3$。 最後啥龍得出對應輸出口 $0$ 和輸出口 $N-1$ 的取貨口是第 $2$ 和 第 $4$ 個取貨口（次序不限），! 2 4 和 ! 4 2 都是可接受的答案。

範例 2

隱藏的對應關係：

在範例 2 中，有 $3$ 個取貨口。 第一次實驗中，速凍仔（從左到右）面前的礦物分別是 藍鐵礦、藍鐵礦、藍鐵礦，報的數為 $[0, 0, 0]$，所以互動器輸出 $0$。 第二次實驗中，速凍仔（從左到右）面前的礦物分別是 藍鐵礦、源礦、藍鐵礦，報的數為 $[0, 1, 2]$，所以互動器輸出 $2$。 第三次實驗中，速凍仔（從左到右）面前的礦物分別是 源礦、源礦、源礦，報的數為 $[0, 0, 0]$，所以互動器輸出 $0$。 最後啥龍得出對應輸出口 $0$ 和輸出口 $N-1$ 的取貨口是第 $0$ 和 第 $1$ 個取貨口（次序不限），! 0 1 和 ! 1 0 都是可接受的答案。

範例 3

隱藏的對應關係：

在範例 3 中，有 $4$ 個取貨口。 第一次實驗中，速凍仔（從左到右）面前的礦物分別是 藍鐵礦、源礦、藍鐵礦、源礦，報的數為 $[0, 1, 2, 3]$，所以互動器輸出 $3$。 最後啥龍得出對應輸出口 $0$ 和輸出口 $N-1$ 的取貨口是第 $0$ 和 第 $3$ 個取貨口（次序不限），! 0 3 和 ! 3 0 都是可接受的答案。

數據範圍與提示

對於所有輸入數據，滿足：

• $3 \leq N \leq 30000$
• 你最多可以發起 $30$ 次實驗，（輸出最終答案不計入實驗次數）。如果你超過這個限制，將得到判為 “Wrong Answer”。

詳細子任務附加限制及分值如下表所示。