Description

Let’s play a game. You are given a row of n balls, each ball is either black or white. Their positions in a row are numbered from 1 to n. You know the total number of balls n, but have no information about the order of their colors. You don’t even know how many white balls are there.

You are allowed to make queries v u (1 ≤ v, u ≤ n). If the ball on position v is black and the ball on position u is white, then these two balls are swapped. Otherwise, nothing happens. Even if the balls are swapped, you don’t get any feedback.

After a number of queries (can be zero) you a required to make a “statement.” “Statement” also consists of two positions v, u. Your goal is to choose positions, that contain two balls of the same color.

In this PRoblem we ask you to print both queries and a “statement”, that comes after them.

A single test can contain several games. Furthermore, all tests except the first one contain 99 game descriptions. In the first game n = 2, in the second — n = 3 … in the last game n = 100.

First test is the same as the sample below.

In all other tests your program must make the right statement at least in 80 games.

Note, that we do not guarantee that the tests are random.

Input

First line contains m — number of games in the test. For every test, except for the first one, m=99.

Remaining lines contain ciphered (except for the first test) order of balls in the row. Thus we guarantee, that the tests are determined beforehand and do not depend on your strategy. Please, do not try to use this data in any way and do not try to decipher it.

Output

Output m game descriptions.

One description consists of (k+1) lines, where k — number of queries made by your program.

First k lines should contain the queries in the following format: ? v u (1 ≤ v, u ≤ n, v ≠ u).

The last line should contain the “statement”: ! v u (1 ≤ v, u ≤ n, v ≠ u).

Total amount of lines (over all games in a test) should not exceed 5×105$5/times 10^5$.

題意

此題應該算是一種交互題

給定 m 組分別長度為 2, 3, 4, …, m的字符串 （你并不知道每個字符串是什么）。每個字符串的均只有 0 或 1 兩種字符，且 0 , 1 個數未知，位置未知。要求在通過一定量的 ? v u 操作之后，請你給出一個 ! v u 表示你認為位置 v 與位置 u 的字符相同。此時機器會判斷是否相同。當你的判斷正確率超過 80% ，則獲得 Accepted ！

操作 ? v u 表示若 v=1 且 u=0 ，則位置上的字符做交換，其余任何情況均不做處理。

分析

要求輸出的 ? v u 和 ! v u 總組數不能超過5×105$5 /times 10^5$ 。

由于 ? v u 操作是單向操作，結合排序可以想到，通過類似冒泡排序的做法可以將原字符串處理成 00...01...11 的形式。若對每組的結果均輸出 ! i i+1 ，則只有在字符 0 和 1 交界的位置會出現判斷失誤的情況，其他情況的判斷均可正確。

由此，該題又變成了一個隨機數的題目。每次輸出的 ! i i+1 失敗的概率為 1/(len(str)-1) 。因此打隨機數正確率 80% 以上是很正常的事情。當然，也可從出題人的角度考慮，只有 21 組數據均卡同一個位置才會 WA 。此時我取了中間兩個值，也能過。

代碼