Max Score: $1500$ Points

Problem Statement

There is a $50 \times 50$ field. The cell at $i$-th row and $j$-th column is denoted $(i, j)$ (0-indexed).
One day, square1001 puts $250$ bombs in this field. In each cell, there is 1 or 0 bomb.
You want to know where the bombs are by asking some questions.

You can ask this question many times.

You can ask the number of bombs in the rectangular area in which upper-left cell is $(a, b)$ and lower-right cell is $(c, d)$.

Please find all bombs' positions asking as few questions as possible.

Note: This problem Input/Output type is special. Please read Input/Output. If you want to use scanf/printf, you have to write fflush(stdout).

Input and output

The first line input is following this format:

$H \ W \ N \ K$

$H, W$ is field size. In this problem, $H = 50$ and $W = 50$.
$N$ is the number of bombs in the field. In this problem, $N = 250$.
$K$ is modulo. This integer uses to answer the state of the field.

After this input, You can ask some questions, following this output format:

$? \ a \ b \ c \ d$

It means that you want to ask the number of bombs in the rectangular area which upper-left cell is $(a, b)$ and lower-right cell is $(c, d)$.

You can know the value of the question, from input in this format:

$p$

$p$ is the result of your question.

Finally, you have to output the answer following this format:

$! \ ans$

The value of $ans$ is $\sum_{i=0}^{H-1} \sum_{j=0}^{W-1} r_{i, j} 2^{iW + j}$ mod $K$. Note: $r_{i, j}$ is the number of bombs in cell $(i, j)$.

Constraints

$H, W = 50$
$N = 250$
$1,000,000,000 \le K \le 1,000,010,000$ ($K$ is random)

Score

There are 5 testcases in the judge.
The $score$ in each testcase is defined by following formula:

$Q$ is the number of questions.
If $Q > 2500$, $score = 0$ (Wrong Answer).
If $930 \le Q \le 2500$, $score = max(\lfloor 125 - 3.2\sqrt{Q - 920} \rfloor, 40)$.
If $880 \le Q < 930$, $score = \lfloor 288 - 22\sqrt{Q - 870} \rfloor$.
If $Q < 880$, $score = min(2860 - 3Q, 300)$.

Sample Input・Output

In the case of the following arrangement, this input / output is conceivable.
This case is $H,W=4$, so this example is not include in testcases.

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

Example of Input・Output

Input from program	Output
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

These question is not always meaningful.

Writer: E869120