Problem C. Counting ones

Author:A. Usmanov   Time limit:1 sec
Input / output:interactive   Memory limit:256 Mb

Statement

This is an interactive problem. Your program will interact with a jury program by sending and receiving particular messages.

The jury has a two-dimensional matrix with N rows and M columns filled with numbers, where each number can be either 1 or 0. Rows are numbered from 1 to N from top to bottom, and columns are numbered from 1 to M from left to right.

Your program can make queries of the form "? Xi Yi Ai Bi", where i is the query number, Xi, Yi represent the coordinates of the top-left corner of the rectangle, denoting the row and column numbers, respectively. On the other hand, Ai, Bi indicate the dimensions of the rectangle, representing the number of rows and columns, respectively. In response to the query, the jury's program will report the number of ones in the rectangle specified by the query.

Each rectangle must be entirely within the matrix, meaning the following inequalities must be satisfied:

1 ≤ Xi, Ai ≤ N and 1 ≤ Yi, Bi ≤ M

Xi + Ai − 1 ≤ N and Yi + Bi − 1 ≤ M

There are also constraints on the sizes of rectangles. The first rectangle must be smaller than the matrix on each side without considering orientation, and each subsequent rectangle must be smaller than the previous one on each side without considering orientation. More formally, the following inequalities must be satisfied:

min(A1, B1) < min(N, M) and max(A1, B1) < max(N, M)

min(Ai, Bi) < min(Ai − 1, Bi − 1) and max(Ai, Bi) < max(Ai − 1, Bi − 1) by i > 1

The goal is to determine the number of ones in the matrix by making any number of queries. It is guaranteed that the values in the matrix are predefined and do not depend on the queries.

Input format

The first line of input contains two integers N and M, the dimensions of the matrix.

Interaction protocol

To make the i-th query, your program should output "? Xi Yi Ai Bi", where Xi, Yi are integers, the coordinates of the top-left corner of the rectangle, row and column numbers respectively. On the other hand Ai, Bi are integers, the dimensions of the rectangle, representing the number of rows and columns, respectively.

After the query, the jury's program responds to your program with an integer S, the number of ones in the specified rectangle.

When your program determines the answer to the task, it should output "! S", where S is an integer, the number of ones in the matrix. After outputting the answer, the program should terminate.

If your program makes incorrect query, it will receive "Presentation error" verdict.

Every query and final output must be a single line ending with single end-of-line (\n). Output buffers must be flushed after every line:

Language C++ Pascal Java Python
Code cout.flush() flush(output) System.out.flush() stdout.flush()

Constraints

10 ≤ N, M ≤ 100

0 ≤ S ≤ 104

Notes on samples

The matrices from the examples are represented in the picture.

Sample tests

No. Standard input Standard output
1
11 13

34

0

0

? 1 1 10 12

? 1 11 11 3

? 10 1 2 10

! 34
2
10 10

38

28

23

16

13

5

3

3

0

? 1 2 9 9

? 3 1 8 8

? 4 2 7 7

? 2 4 6 6

? 5 5 5 5

? 3 7 4 4

? 8 8 3 3

? 1 1 2 2

? 10 10 1 1

! 44

0.122s 0.022s 15