AT_nupc2024_k A Shortcut

この問題は **インタラクティブ** な問題（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）です。 整数 $ N $ が与えられます。また、ジャッジは次のように構成される $ N $ 頂点の無向グラフ $ G $ を秘匿しています。 - $ G $ の頂点にはそれぞれ $ 1, 2, \dots , N $ の番号が振られている。 - すべての $ 1 \le i < N $ を満たす整数 $ i $ に対して、頂点 $ i $ と頂点 $ i+1 $ の間に辺が存在する。 - $ y - x > 1 $ かつ $ 1 \le x, y \le N $ を満たす整数の組 $ (x, y) $ が **ただ 1 つ** 存在し、頂点 $ x $ と頂点 $ y $ の間に辺が存在する。 - 上記の $ N $ 本の辺の他に辺はない。 あなたは、 $ G $ について以下のクエリを送ることができます。 - $ 2 $ つの頂点番号 $ p, q $ を選ぶ。頂点 $ p $ から頂点 $ q $ への最短経路の長さ（経路上の辺の数）を質問する。 $ \lceil \log_2 N + 1 \rceil $ 回以内のクエリで $ (x, y) $ を特定してください。 なお、ジャッジは適応的 (adaptive) ではなく、各テストケースに対して固定された $ (x, y) $ を持っています。 テストケースが $ T $ 個与えられるので、それぞれについて $ (x, y) $ を特定してください。 ### Input & Output Format 最初に、標準入力に整数 $ T $ が与えられます。 > $ T $ 次に、 $ T $ 個のテストケースが与えられます。各テストケースは次の形式で与えられます。 まず、整数 $ N $ が与えられます。 > $ N $ 次に、 $ \lceil \log_2 N +1 \rceil $ 回までクエリを行うことができます。 各クエリは以下の形式で標準出力に出力してください。ここで、 $ p, q $ は $ 1 \le p, q \le N $ を満たす整数である必要があります。 > ? $ p $ $ q $ これに対する応答は、次の形式で標準入力から与えられます。 > $ \mathrm{dist}(p, q) $ ここで、 $ \mathrm{dist}(p, q) $ は頂点 $ p $ から頂点 $ q $ までの最短経路の長さを表します。ただし、不正なクエリを行った場合、またはクエリ回数が $ \lceil \log_2 N + 1 \rceil $ 回を超えた場合、ジャッジは `-1` を出力します。 ジャッジが `-1` を出力した場合、残りのテストケースに関わらずプログラムはすでに不正解とみなされています。この場合、ただちにプログラムを終了してください。 $ (x, y) $ を回答する場合、次の形式で標準出力に出力してください。この出力はクエリ回数に含まれません。 > ! $ x $ $ y $ その後、次のテストケースが存在する場合は、次のテストケースに引き続き回答してください。最後のテストケースに回答した後は、プログラムを終了してください。

N/A

N/A

### 注意点 - 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。 - 不正な出力や動作に対するジャッジは不定である可能性があります。 - $ (x, y) $ は対話の前に固定されており、対話内容によって変化することはありません。 ### 入出力例 入力 出力 説明 `2` まず整数 $ T $ が与えられます。 `10` $ 1 $ つ目のテストケースが始まりました。各テストケースでは、まず整数 $ N $ が与えられます。 `? 1 10` $ p = 1, q = 10 $ として質問を行います。 `6` $ \mathrm{dist}(1, 10)=6 $ が与えられます。 `? 8 6` $ p = 8, q = 6 $ として質問を行います。 `2` $ \mathrm{dist}(8, 6)=2 $ が与えられます。 `? 3 7` $ p = 3, q = 7 $ として質問を行います。 `1` $ \mathrm{dist}(3, 7)=1 $ が与えられます。 `! 3 7` 答えとして $ (x, y) = (3, 7) $ を出力します。この出力は正解です。 `3` $ 2 $ つ目のテストケースが始まりました。まず整数 $ N $ が与えられます。 `? 1 2` $ p = 1, q = 2 $ として質問を行います。 `1` $ \mathrm{dist}(1, 2)=1 $ が与えられます。 `! 1 3` 答えとして $ (x, y) = (1, 3) $ を出力します。この出力は正解です。テストケースは以上なのでプログラムを終了させます。 ### Constraints - $ 1\leq T\leq 10^3 $ - $ 3\leq N\leq 10^9 $ - $ 1 \le x < y \le N $ - $ y - x > 1 $ - $ T, N, x, y $ は整数