CF1493F.Enchanted Matrix

This is an interactive problem.

There exists a matrix $a$ of size $n \times m$ ($n$ rows and $m$ columns), you know only numbers $n$ and $m$. The rows of the matrix are numbered from $1$ to $n$ from top to bottom, and columns of the matrix are numbered from $1$ to $m$ from left to right. The cell on the intersection of the $x$-th row and the $y$-th column is denoted as $(x, y)$.

You are asked to find the number of pairs $(r, c)$ ($1 \le r \le n$, $1 \le c \le m$, $r$ is a divisor of $n$, $c$ is a divisor of $m$) such that if we split the matrix into rectangles of size $r \times c$ (of height $r$ rows and of width $c$ columns, each cell belongs to exactly one rectangle), all those rectangles are pairwise equal.

You can use queries of the following type:

• ? $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$) — to check if non-overlapping subrectangles of height $h$ rows and of width $w$ columns of matrix $a$ are equal or not. The upper left corner of the first rectangle is $(i_1, j_1)$. The upper left corner of the second rectangle is $(i_2, j_2)$. Subrectangles overlap, if they have at least one mutual cell. If the subrectangles in your query have incorrect coordinates (for example, they go beyond the boundaries of the matrix) or overlap, your solution will be considered incorrect.

You can use at most $ 3 \cdot \left \lfloor{ \log_2{(n+m)} } \right \rfloor$ queries. All elements of the matrix $a$ are fixed before the start of your program and do not depend on your queries.

这是一个交互式问题。

存在一个大小为 $n \times m$ 的矩阵 $a$（共 $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$ 的所有元素在你的程序开始运行前即已固定，且不依赖于你的任何查询。

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 1000$) — the number of rows and columns, respectively.

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 1000$），分别表示行数和列数。

When ready, print a line with an exclamation mark ('!') and then the answer — the number of suitable pairs $(r, c)$. After that your program should terminate.

准备就绪后，输出一行，包含一个感叹号（'!'）以及答案——即满足条件的数对 $(r, c)$ 的数量。之后，你的程序应终止。

In the example test the matrix $a$ of size $3 \times 4$ is equal to:

1 2 1 2
3 3 3 3
2 1 2 1

在样例测试中，$3 \times 4$ 的矩阵 $a$ 为：

1 2 1 2
3 3 3 3
2 1 2 1