Legend
Link ( extrm{to Codeforces})。
Editorial
这个询问次数限制非常鬼畜：(3 cdot lfloor log_2 (n+m) floor)，而且答案的 ((r,c)) 一定满足 (r|n,c|m) 看起来就跟质因子的指数和和有什么奇怪的关系。
先来分析一下题目。我们画一个小矩形，然后把它复制若干份平铺，看看能不能发现什么性质。
Observation 1: 行列是独立的，我们只要求出行和列的方案然后乘起来就行了。
显然，但证明我还没想到什么好办法。
于是 2D 问题变成了序列问题，也就是现在有一个长 (n) 的序列，你每次可以询问两个不相交子串，求它的最小周期。
最小周期？考虑怎么判断一个长度 (k) 是不是 (n) 的周期，根据定义来说，必须这样：
- 将 (k) 个元素捆在一起，则 (frac{n}{k}) 个元素完全一致。
正好交互器支持询问元素是否一致，看来这就是正解的方向！但是两个两个问太慢了，怎么办呢？
你如果对于字符串理论非常熟悉，那么你可能会想到 border 可以用来判定周期，只需要询问一个前缀和后缀是否相等就行了。而对于 border 不相交的情况，我们直接询问就行。但是 border 是有可能相交的，如下图。（我们认为周期长度是 (4)，X. 交替仅为美观）
XXXX....XXXX....XXXX....XXXX
[______________________]
[______________________]
我们不能询问相交的区间，怎么办办呢？你可能会想能不能递归判定呢？
不过这复杂度太高，我们必须要一个常数次询问的做法。
Observation 2：可以在最多 (2) 次操作的情况下判定一个长度是不是周期。
下给出构造方法：
XXXX....XXXX....XXXX....XXXX
[_____1____]
[_____2____]
[_____3____]
聪明的人类智慧告诉我们，我们可以先问 (1,2)，再问 (2,3)。如果 (1=2=3)，那么长度 (4) 就可以被判定了。
等于说我们用 (1)，强行比较了原本相交的 (2,3)。我们知道了 (2,3) 这个的周期可以是长度 (4)，然后我们又把前缀复制了一份丢在前面，那么长度 (4) 肯定也是周期。这样就完成了判定。
所以我们可以在最多 (2) 次操作的情况下判定一个长度是不是周期。
Observation 3：如果长度 (a) 是答案，(b) 也是答案，则 (gcd(a,b)) 一定是答案。
根据周期的理论，我们可以得出它是真的。
所以说，我们初始令最短周期是 (n)，尝试每次从小到大消除它的一个质因子即可。
这样复杂度是什么？设当前正在消除的质因子是 (P)。
我们也就要检测 (frac{n}{P}) 是否是周期。
- 如果是，则 (n gets frac{n}{P})。
- 如果不是，换下一个质因子。
Observation 4：上述算法时间查询次数不超过 (lfloor log_3 16 log_2 n floor+4)
我们发现 (P=2) 时只需要 (1) 次查询，(P>3) 时需要 (2) 次查询。
所以说我们结束这个算法至多需要 (2lfloor log_3 n floor) 次询问。如果假设题目中的 (n,m) 同阶，则需要 (4lfloor log_3 n floor) 次询问。
经过一番高中必修一（换底公式）数学推导，我们得到 (4lfloor log_3 n floor le log_3 16 log_2 n)。
<这里本该有张图>
其中红色的代表题目中的限制 (3 lfloor log_2 n floor+3)。不难发现，只有当 (n=1,2,3) 的时候我们的算法可能会挂，但是发现由于我们的不等式是做了过剩估计的，其实并不会挂。
（至于怎么证 (n e m) 的呢，我不会）
Code
#include <bits/stdc++.h>
#define debug(...) fprintf(stderr ,__VA_ARGS__)
#define __FILE(x)
freopen(#x".in" ,"r" ,stdin);
freopen(#x".out" ,"w" ,stdout)
#define LL long long
const int MX = 1e3 + 23;
const LL MOD = 998244353;
int read(){
char k = getchar(); int x = 0;
while(k < '0' || k > '9') k = getchar();
while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
return x;
}
int qpow(int a ,int b){
int r = 1;
for(int i = 1 ; i <= b ; ++i) r *= a;
return r;
}
int qc;
int ask(int h ,int w ,int x1 ,int y1 ,int x2 ,int y2){
++qc;
// return 1;
printf("? %d %d %d %d %d %d
" ,h ,w ,x1 ,y1 ,x2 ,y2); fflush(stdout);
return read();
}
int n ,m;
int getit(int a ,int x){
int r = 0;
for(int i = a ; i <= x ; i += a)
r += x % i == 0;
return r;
}
int main(){
n = read() ,m = read();
int a1 = m;
for(int i = 2 ; i <= m ; ++i){
int is_prime = true;
for(int j = 2 ; j * j <= i ; ++j){
if(i % j == 0) is_prime = false;
}
if(!is_prime) continue;
while(a1 % i == 0){
int tmp = a1 / i; // 看看长度为 tmp 行不行
// 分成 i 段了
int ok = 0;
#define id(x) (((x) - 1) * tmp + 1)
if(i == 2) ok = ask(n ,tmp ,1 ,id(1) ,1 ,id(2));
else ok = ask(n ,i / 2 * tmp ,1 ,id(1) ,1 ,id(i / 2 + 1))
&& ask(n ,i / 2 * tmp ,1 ,id(1) ,1 ,id(i / 2 + 2));
if(ok){
a1 /= i;
}
else{
break;
}
}
}
int a2 = n;
for(int i = 2 ; i <= n ; ++i){
int is_prime = true;
for(int j = 2 ; j * j <= i ; ++j){
if(i % j == 0) is_prime = false;
}
if(!is_prime) continue;
while(a2 % i == 0){
int tmp = a2 / i; // 看看长度为 tmp 行不行
// 分成 i 段了
int ok = 0;
#define id(x) (((x) - 1) * tmp + 1)
if(i == 2) ok = ask(tmp ,m ,id(1) ,1 ,id(2) ,1);
else ok = ask(i / 2 * tmp ,m ,id(1) ,1 ,id(i / 2 + 1) ,1)
&& ask(i / 2 * tmp ,m ,id(1) ,1 ,id(i / 2 + 2) ,1);
if(ok){
a2 /= i;
}
else{
break;
}
}
}
printf("! %d
" ,getit(a1 ,m) * getit(a2 ,n)); fflush(stdout);
debug("query %d times %d %d
" ,qc ,a2 ,a1);
return 0;
}