Задача C. Counting ones ≡

Условие

Данная задача является интерактивной. Ваша программа будет взаимодействовать с программой жюри путем отправки и приема сообщений определенного вида.

У жюри есть двумерная матрица N строк на M столбцов заполненная числами, где каждое число может быть либо 1, либо 0. Строки имеют нумерацию с 1 по N сверху вниз, столбцы — с 1 по M слева направо.

Ваша программа может делать запросы вида "? Xi Yi Ai Bi", где i — номер запроса, X_i, Y_i — координаты левого верхнего угла прямоугольника, номера строки и столбца соответственно, а A_i, B_i — размеры сторон прямоугольника, количество строк и столбцов соответственно. В ответ на запрос программа жюри сообщит о количестве единиц в прямоугольнике из запроса.

Каждый из прямоугольников должен целиком лежать внутри матрицы, то есть должны выполняться следующие неравенства:

1 ≤ X_i, A_i ≤ N и 1 ≤ Y_i, B_i ≤ M

X_i + A_i − 1 ≤ N и Y_i + B_i − 1 ≤ M

Также имеются ограничения на размеры прямоугольников. Первый прямоугольник должен быть меньше матрицы по каждой из сторон без учета ориентации, а каждый последующий прямоугольник должен быть меньше предыдущего по каждой из сторон без учета ориентации. Более формально должны выполняться следующие неравенства:

min(A₁, B₁) < min(N, M) и max(A₁, B₁) < max(N, M)

min(A_i, B_i) < min(A_i − 1, B_i − 1) и max(A_i, B_i) < max(A_i − 1, B_i − 1) для i > 1

Требуется определить количество единиц в матрице, сделав любое количество запросов. Гарантируется, что значения чисел в матрице определены заранее и не зависят от запросов.

Формат входных данных

В первой строке входных данных записаны целые числа N и M — размеры матрицы.

Протокол взаимодействия

Чтобы сделать i-й запрос, ваша программа должна вывести "? Xi Yi Ai Bi", где X_i, Y_i — целые числа, координаты левого верхнего угла прямоугольника, номера строки и столбца соответственно, а A_i, B_i — целые числа, размеры сторон прямоугольника, количество строк и столбцов соответственно.

После запроса программа жюри отвечает вашей программе целым числом S — количеством единиц в прямоугольнике из запроса.

Когда ваша программа определила ответ на задачу, она должна вывести "! S", где S — целое число, количество единиц в матрице. После вывода ответа программа должна завершиться.

Если ваша программа сделает недопустимый запрос, то она получит вердикт "Presentation error".

Каждый запрос и вывод окончательного результата должен быть одиночной строкой заканчивающейся одиночным переводом строки (\n). Буфер вывода необходимо сбрасывать после каждой строки:

Ограничения

10 ≤ N, M ≤ 100

0 ≤ S ≤ 10⁴

Пояснение к примерам

Матрицы из примеров представлены на картинке.

Примеры тестов

11 13

34

0

0

? 1 1 10 12

? 1 11 11 3

? 10 1 2 10

! 34

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