入出力

1. まず, あなたは, 以下のような入力を受け取らなければならない.

N

N は, 平面上に存在する円の個数を表す.

2. 次に, あなたは質問をしなければならない. まず, 質問をするためには以下のように出力しなければならない.

? p q

あなたは '?', p, q を空白区切りで一行に出力しなければならない. これは, 座標 (p, q) はいくつの円の内部に含まれているか, という質問をすることを意味する. p, q は小数でもよいが, 絶対値が 5 \ 000 以下でなければならない.

3. 質問への答えは, 以下のようにしてジャッジから入力として受け取らなければならない.

R

R は, 質問した座標は何個の円の内部に含まれているかを表す整数である. 質問への答えが終わったら, 2. もしくは 4. に行かなければならない.

4. 答えが分かったら, 分かったタイミングで質問の代わりに解答を行わなければならない. 解答をするためには, 以下のような出力を行わなければならない.

!
x_1 y_1 r_1
x_2 y_2 r_2
...
x_N y_N r_N

(x_i, y_i) は i 個目の円の中心座標, r_i は i 個目の円の半径を意味する.

解答を行う際には, N+1 行にわたって出力しなければならない.

1 行目には, '!' と出力しなければならない.

2 行目からは, N 行にわたって円の情報 (x_i, y_i, r_i) をその順に空白区切りで出力しなければならない. ただし, 出力する順番は中心座標の x 座標の小さい順, x 座標が同じであれば y 座標の小さい順に出力しなければならない.

制約

• N は 1 以上 20 以下の整数.
• 円の座標 (x_i, y_i) と円の半径 r_i は, 問題文中に書かれている制約を満たす.
• 全てのケースは, 制約の範囲内で, 一様な確率でランダムに生成されたものである. 具体的には, それぞれの円に対して, まず中心座標が (-1000, -1000) から (1000, 1000) までの 4004001 個の中から一様な確率分布でランダムに選ばれ, 次に半径が 200 から 1000 までの 801 通りの選択肢の中から一様な確率分布で選ばれる.

注意

• 出力形式を間違えたりした場合にジャッジ結果は不定である. (WA とは限らない)
• また, 出力の最後に flush をする必要があり, そうしない場合 TLE となる場合がある.
• あなたは, 50 \ 000 回を超える質問をしてはならない.

小課題 / 得点

小課題1 [ 200点 ]

• N = 1 である.
• 小課題 1 のケースは 10 個ある. 10 個全てのケースに対して, 50 \ 000 回以内の質問で答えを求めることができれば, 正解となる.

小課題2 [ 1 \ 100点 ]

• N = 20 である.
• 小課題 2 のケースは 20 個ある. 20 個全てのケースで 50 \ 000 回以内の質問で答えを求めることができれば正解となるが, 質問回数によって下記のように得点が変わる.

一番多くの質問回数を要したケースにおける質問回数を L* とおくとき, 得点は以下のように変動する.

• 25 \ 001 \leq L* \leq 50 \ 000 のとき, 200 点.
• 9 \ 001 \leq L* \leq 25 \ 000 のとき, 280 点.
• 3 \ 001 \leq L* \leq 9 \ 000 のとき, 350 点.
• 2 \ 001 \leq L* \leq 3 \ 000 のとき, 450 点.
• 601 \leq L* \leq 2 \ 000 のとき, 300 + floor(\frac{480000}{L*}) の 1 の位を切り捨てて 10 の位までの概数にした得点.
• L* \leq 600 のとき, 1 \ 100 点満点.