题目描述

さて, このsquare869120Contest #3も, 最終問題となってしまった。
square1001氏は, 最終兵器として, あるダンジョンに爆弾を仕掛けた。
そのダンジョンは, 左上のマスが $(0,0)$, 右下のマスが $(49,49)$ の $50\ \times\ 50$ の大きさである。

その中には, 250個の爆弾が仕掛けられている。位置はすべて違うマスである。
あなたは, 全ての爆弾の位置を知ることで, そのダンジョンから脱出できる。
「そんなん、どうやって知ればいいんだよ！ 全く分かんねぇじゃないか！助けてぇぇぇぇぇ！」

しかし、あなたは以下の質問を何回かできる。

• 左上のマス $(a,\ b)$, 右下のマス $(c,\ d)$ の区間に何個爆弾があるかを聞くことができる。

しかし, 質問回数が多くなればなるほど, 爆弾の爆発する確率が高くなり, すなわち生存確率が下がる。
そのため, できるだけ少ない質問回数で爆弾250個の配置を当ててほしい。(その方が得点が高い)
あなたの挑戦を待っている。

Input & Output Format

最初, 以下のように入力される。

$H\ W\ N\ K$

• $H,\ W$ はダンジョンの大きさである。この問題では, $H,\ W\ =\ 50$ である。
• $N$ はダンジョンの中に含まれる爆弾の数である。この問題では, $N\ =\ 250$ である。
• $K$ は最終的な盤面の状態を出力するために使う整数である。

次に, 次のような質問を何回かすることができる。
質問は以下のような形式で出力することによってできる。

$?\ a\ b\ c\ d$

これは, 左上のマス $(a,\ b)$, 右下のマス $(c,\ d)$ の区間に存在する爆弾の数を聞くことである。

また, 質問の返答は, 以下のような出力で行われる。

$p$

$p$ は, 質問で聞いた区間に存在する爆弾の総数である。

また, 答えが分かった時に, 以下のような出力をしなければならない。

$!\ ans$

ただし, $ans$ は以下の値であり, $r_{i,\ j}$ は, マス $(i,\ j)$ にある爆弾の個数である。

• $ ans\ =\ \sum_{i=0}^{H-1}\ \sum_{j=0}^{W-1}\ r_{i,\ j}\ 2^{iW\ +\ j} $ mod $K$

提示

制約

• $H,\ W\ =\ 50$
• $N\ =\ 250$
• $1,000,000,000\ \le\ K\ \le\ 1,000,01,000$ ($K$はランダムに与えられる)

得点

5つのテストケースがある。各テストケースに対する得点は, 以下のように計算される。

• 質問回数を $Q$ とする。
• $Q\ >\ 2500$ のとき, $0$ 点 (Wrong Answer) となる。
• $930\ \le\ Q\ \le\ 2500$ のとき, $ score\ =\ max(\lfloor\ 125\ -\ 3.2\sqrt{Q\ -\ 920}\ \rfloor,\ 40) $ となる。
• $880\ \le\ Q$Q

入出力例1

例えば, 以下のような配置の場合、以下のような入出力が考えられる。
ただし, この場合 $H\ =\ W\ =\ 4,\ N\ =\ 4$ なので, 実際のテストケースには存在しない。

H=4, W=4, N=4
1001
0000
0010
0100

入出力として考えられる例
プログラムへの入力 プログラムの出力 4 4 4 1000000007 ? 0 0 0 1 1 ? 0 1 0 2 0 ? 0 3 1 3 1 ? 2 1 3 2 2 ? 2 2 2 2 1 ! 9225 ただし, 必ずしも意味のある質問をしているとは限りません。
また, これらの情報で必ずしも盤面が把握できるとは限らず, エスパーをすることも許されはします。