Это интерактивная задача.
Есть матрица \(a\) размера \(n \times m\) (\(n\) строк и \(m\) столбцов), вам известны только числа \(n\) и \(m\). Строки матрицы пронумерованы от \(1\) до \(n\) сверху вниз, а столбцы от \(1\) до \(m\) слева направо. Клетка матрицы на пересечении строки \(x\) и столбца \(y\) обозначается как \((x, y)\).
Необходимо найти количество пар \((r, c)\) (\(1 \le r \le n\), \(1 \le c \le m\), \(r\) — делитель \(n\), \(c\) — делитель \(m\)) таких, что если разбить матрицу на прямоугольники \(r \times c\) (высотой \(r\) строк и шириной \(c\) столбцов, каждая клетка принадлежит ровно одному прямоугольнику), все эти прямоугольники будут попарно равны между собой.
Вам доступны следующие запросы:
- ? \(h\) \(w\) \(i_1\) \(j_1\) \(i_2\) \(j_2\) (\(1 \le h \le n\), \(1 \le w \le m\), \(1 \le i_1, i_2 \le n\), \(1 \le j_1, j_2 \le m\)) — узнать, равны ли непересекающиеся подпрямоугольники матрицы \(a\) высотой \(h\) строк и шириной \(w\) столбцов, левая верхняя клетка первого из которых — \((i_1, j_1)\); левая верхняя клетка второго подпрямоугольника — \((i_2, j_2)\). Подпрямоугольники пересекаются, если у них есть хотя бы одна общая клетка. Если подпрямоугольники в вашем запросе будут иметь некорректные координаты (например, выходить за границы матрицы) или пересекаться, ваше решение будет считаться неверным.
Вы можете сделать не более \( 3 \cdot \left \lfloor{ \log_2{(n+m)} } \right \rfloor\) запросов. Все элементы матрицы \(a\) зафиксированы до запуска вашей программы и не зависят от ваших запросов.
Выходные данные
Когда будете готовы, выведите строку, содержащую восклицательный знак («!») и затем ответ на задачу — количество подходящих пар \((r, c)\). После этого ваша программа должна завершиться.
Протокол взаимодействия
Чтобы сделать запрос, выведите строку вида «? \(h\) \(w\) \(i_1\) \(j_1\) \(i_2\) \(j_2\)», в которой целые числа — высота, ширина и координаты верхних левых углов непересекающихся прямоугольников, про которые вы хотите узнать, равны они или нет.
После каждого запроса считайте одно целое число \(t\) (\(t\) равно \(0\) или \(1\)). Если заданные подпрямоугольники равны, \(t=1\), иначе \(t=0\).
В случае, если ваш запрос имеет неверный формат, или вы сделали более \(3 \cdot \left \lfloor{ \log_2{(n+m)} } \right \rfloor\) запросов, вы получите вердикт «Неправильный ответ».
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Гарантируется, что матрица \(a\) зафиксирована и не будет меняться в процессе взаимодействия.
Формат взломов
Для взломов необходимо использовать следующий формат.
В первой строке находятся два целых числа \(n\) и \(m\) (\(1 \le n, m \le 1000\)) — количество строк и столбцов в матрице соответственно.
В каждой из следующих \(n\) строк находятся по \(m\) целых чисел — элементы матрицы \(a\). Все элементы матрицы должны являться целыми числами между \(1\) и \(n \cdot m\) включительно.
Примечание
В тесте из примера матрица \(a\) размера \(3 \times 4\) следующая:
1 2 1 2
3 3 3 3
2 1 2 1
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
1
1
1
0
|
? 1 2 1 1 1 3
? 1 2 2 1 2 3
? 1 2 3 1 3 3
? 1 1 1 1 1 2
! 2
|