これはインタラクティブ問題です。 クエリ回数の上限は $18\,000$ 回です。
ジャッジはちょうど 1000 桁の二進数字からなる秘密の文字列を持っています。この問題の各テストでは、文字列はあらかじめ固定されており、変化しません。クエリを用いてこの文字列を求めてください。
各クエリでは、尋ねる区間 $[a, b]$（$1 \le a \le b \le 1000$）を選びます。その後、ジャッジはコインを投げ、次の2つの値のいずれかを、それぞれ 50% の確率で返します。
- 区間 $[a, b]$ 内の 1 の個数。
- $0$ から $b - a + 1$ までの値のうち、その区間内の 1 の個数と等しくない値を一様ランダムに選んだもの。
同じクエリを2回使うことはできません。この問題で用いられるすべての乱数は一様で、独立です。
インタラクション
参加者のプログラムは、次のいずれかの形式のコマンドを出力してジャッジのプログラムとやり取りしなければなりません。
? a b。区間 $[a, b]$ へのクエリです。ジャッジのプログラムは答えとして整数を1つ出力します。それは 50% の確率で区間 $[a, b]$ 内の 1 の個数となり、そうでなければ $0$ から $b - a + 1$ までの、その個数とは異なるランダムな値となります。! ans。問題の答えです。ansは 0 と 1 からなる長さ 1000 の文字列です。このコマンドの後、参加者のプログラムは直ちに終了してください。
入出力例
入力 1
2 3 3 1 3
出力 1
? 1 3 ? 1 5 ? 3 5 ? 2 3 ? 2 5 ! 01101
注記
上の例は形式を示すためだけのものです。この例では文字列の長さは 5 です。実際の最初のテストでも、それ以外のすべてのテストでも、推測する文字列の長さはちょうど 1000 です。