说句闲话，这个 idea 是我在去年暑假的一天里梦见的。

看到我们只能询问离散对数方程的解，不难想到原根。因为原根有一个很好的性质：在模 $p$ 意义下，若 $g$ 为 $p$ 的原根，$\forall 1 \leq a < p, g^x \equiv a \pmod p$ 是一定有解的。

但题目没有给我们 $p$ 的原根，考虑猜出原根 $g$。如果直接从 $1$ 开始枚举 $g$ 并判断，最坏情况下最小的 $g$ 是 $O(p^{\frac{1}{4}})$ 的，无法通过所有数据。但注意到对于质数 $p$，其原根个数为 $\varphi(\varphi(p))$，这个数字大概在 $\frac{p}{3} \sim \frac{p}{2}$ 之间，也就是说，我们期望 $3$ 次左右就能随机出一个 $p$ 的原根。

现在考虑判断一个数 $g_0$ 是否为 $p$ 的原根。首先我们通过 $g_0^x \equiv 0 \pmod p$ 判掉 $g_0$ 为 $p$ 的倍数的情况。尽管我们不能知道 $p$ 是什么，但注意到上面提到的原根的性质，我们可以随机若干正整数 $s$，仍然先判掉 $s$ 为 $p$ 的倍数的情况，然后看 $g_0^x \equiv s \pmod p$ 是否有解，如果无解，则 $g_0$ 不为 $p$ 的原根。考虑到所有非 $p$ 的原根的 $g_0$ 都存在一个 $t$，使 $g_0 \equiv g^t \pmod p$ 且 $\gcd(t, \varphi(p)) > 1$，当 $ut \equiv x \pmod{\varphi(p)}$ 无解即 $\gcd(t, \varphi(p)) \not\mid x$ 时可以判定 $g_0$ 不为 $p$ 的原根。也就是说，假如无解，我们期望 $2$ 次左右随机出一个足以判定 $g_0$ 不满足条件的 $s$。为了保险，这里我们可以取 $10$ 次。

求完原根后，我们来构造方程。由于题目允许我们对非常大的 $a, b$ 做出询问（不超过 $10^{1.8 \times 10^{19}}$ 量级），考虑随机一个 $x_0$，令 $F(x) = x$，$G(x) = x^{x_0}$，$u = v = g$。由于 $p$ 为质数，根据欧拉定理，我们有 $x_0 \equiv x \pmod{\varphi(p)}$，进而可以得到 $\varphi(p) \mid (x_0 - x)$。

于是我们把询问次数卡满，对每次得到的 $x_0 - x$ 求 $\gcd$，将最终所得的值 $+ 1$ 即可得到 $p$。这样看上去很不靠谱，但实际上极大概率可以得到一个合法的解，因为我们可以将 $x_0 \bmod \varphi(p)$ 视为一个随机数且存在下面这个结论：

• 两个 $O(n)$ 级别的随机数的 $\gcd$ 的期望大小是 $O(\ln n)$ 的。

证明：$O(\dfrac{\displaystyle\sum_{i = 1}^n \sum_{j = 1}^n \gcd(i, j)}{n^2}) = O(\dfrac{\displaystyle\sum_{d = 1}^n \varphi(d) \lfloor \frac{n}{d} \rfloor^2}{n^2}) = O(\displaystyle\sum_{d = 1}^n \frac{\varphi(d)}{d^2}) \leq O(\displaystyle\sum_{d = 1}^n \frac{1}{d}) = O(\ln n)$。

于是我们只需要询问期望 $O(\ln^* \frac{w}{p})$（$w = 10^{18}$）次即期望 $4$ 次左右就可以得到 $p$ 的值。当然因为两边值域不一定对称，实测在保证可以得到答案的前提下需要 $15$ 次。

最终我们只需要期望 $70$ 次左右的询问即可得到答案，实测在保证可以得到答案的前提下一般需要 $50 \sim 80$ 次左右，最大需要 $100$ 次左右。

代码：

#include <iostream>
#include <vector>
#include <iostream>
#include <vector>
#include <random>
#include <ctime>

using namespace std;

typedef long long ll;

const int N = 50 + 7;
const ll M = 1e18;
int t, cnt = 0;
ll bucket[N];
mt19937 e(time(NULL));
uniform_int_distribution<ll> rnd(1, M);

inline ll ask(int n, int m, ll u, ll v, vector<ll> c, vector<ll> d, vector<ll> e, vector<ll> f){
	ll ans = 0;
	cout << "ask " << n << " " << m << " " << u << " " << v << "\n";
	for (register int i = 0; i < n; i++){
		cout << c[i] << " ";
	}
	cout << "\n";
	for (register int i = 0; i < m; i++){
		cout << d[i] << " ";
	}
	cout << "\n";
	for (register int i = 0; i < n; i++){
		cout << e[i] << " ";
	}
	cout << "\n";
	for (register int i = 0; i < m; i++){
		cout << f[i] << " ";
	}
	cout << endl;
	cin >> ans;
	return ans;
}

inline ll make(){
	ll ans;
	do {
		ans = rnd(e);
		t--;
	} while (ask(1, 1, ans, 0, vector<ll>{1}, vector<ll>{0}, vector<ll>{1}, vector<ll>{0}) != -1);
	return bucket[++cnt] = ans;
}

ll gcd(ll a, ll b){
	return b == 0 ? a : gcd(b, a % b);
}

inline void answer(ll p_){
	cout << "answer " << p_ << endl;
}

int main(){
	ll g, phi_p = 0;
	cin >> t;
	while (true){
		int pos = 1;
		bool flag = true;
		g = make();
		for (register int i = 1; i <= 10; i++){
			if (pos > cnt){
				make();
			} else if (bucket[pos] == g){
				pos++;
				if (pos > cnt) make();
			}
			t--;
			if (ask(1, 1, g, bucket[pos], vector<ll>{1}, vector<ll>{1}, vector<ll>{1}, vector<ll>{1}) == -1){
				flag = false;
				break;
			}
			pos++;
		}
		if (flag) break;
	}
	while (--t >= 0){
		ll x0 = rnd(e), x = ask(1, 1, g, g, vector<ll>{1}, vector<ll>{x0}, vector<ll>{1}, vector<ll>{1});
		phi_p = gcd(phi_p, x0 - x);
	}
	answer(phi_p + 1);
	return 0;
}