CF2109C3.Hacking Numbers (Hard Version)

这是该问题的困难版本。在此版本中，你能发送的指令限制将在题目描述中说明。只有在解决所有版本的问题后才能进行 hack。

这是一个交互式问题。

欢迎，决斗者们！在这个交互式挑战中，存在一个未知整数 $x$（$1 \le x \le 10^9$）。你需要通过利用"Mathmech"怪兽的力量，将其变为输入中给定的整数 $n$。你可以发送以下指令之一：

指令	约束条件	结果	更新操作	裁判响应
"add $y$"	$-10^{18} \le y \le 10^{18}$	$\mathrm{res} = x + y$	若 $1 \le \mathrm{res} \le 10^{18}$，则 $x \leftarrow \mathrm{res}$	"1"
			否则 $x \leftarrow x$	"0"
"mul $y$"	$1 \le y \le 10^{18}$	$\mathrm{res} = x \cdot y$	若 $1 \le \mathrm{res} \le 10^{18}$，则 $x \leftarrow \mathrm{res}$	"1"
			否则 $x \leftarrow x$	"0"
"div $y$"	$1 \le y \le 10^{18}$	$\mathrm{res} = x/y$	若 $y$ 整除 $x$，则 $x \leftarrow \mathrm{res}$	"1"
			否则 $x \leftarrow x$	"0"
"digit"	—	$\mathrm{res} = S(x)$ $^{\text{∗}}$	总是 $x \leftarrow \mathrm{res}$	"1"

设 $f(n)$ 为最小整数，使得对于所有 $x$（$1 \le x \le 10^9$），都存在一个由 $f(n)$ 条指令组成的序列能将 $x$ 转换为 $n$。你事先不知道 $x$ 的值。你需要找到这样的 $f(n)$，使得无论 $x$ 是多少，你都能用最多 $f(n)$ 条指令将其转换为 $n$。

你的任务是用最多 $f(n)$ 条指令将 $x$ 变为 $n$。

$^{\text{∗}}$ $S(n)$ 是一个函数，返回非负整数 $n$ 的各位数字之和。例如，$S(123) = 1 + 2 + 3 = 6$。

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 5000$）。接下来是测试用例描述。

每个测试用例的第一行也是唯一一行包含一个整数 $n$（$1 \le n \le 10^9$）。

每个测试用例的交互从读取整数 $n$ 开始。

发送指令时，按以下格式输出一行：

• "add $y$"：将 $x$ 加上整数 $y$（$-10^{18} \le y \le 10^{18}$）。裁判将输出"1"表示 $x + y$ 在 $[1, 10^{18}]$ 内（成功），否则输出"0"。若成功，更新 $x \leftarrow x + y$。
• "mul $y$"：将 $x$ 乘以正整数 $y$（$1 \le y \le 10^{18}$）。裁判将输出"1"表示 $x \cdot y$ 在 $[1, 10^{18}]$ 内（成功），否则输出"0"。若成功，更新 $x \leftarrow x \cdot y$。
• "div $y$"：将 $x$ 除以正整数 $y$（$1 \le y \le 10^{18}$）。裁判将输出"1"表示 $y$ 是 $x$ 的因数（成功），否则输出"0"。若成功，更新 $x \leftarrow \frac{x}{y}$。
• "digit"：将 $x$ 设为其各位数字之和。裁判总是输出"1"并更新 $x \leftarrow S(x)$。

注意指令区分大小写。

当你确定 $x$ 等于 $n$ 时，按以下格式输出一行：

• "!"——裁判将输出"1"表示 $n$ 等于 $x$，否则输出"-1"。

注意回答指令不计入指令限制。

如果你的程序对一个测试用例发送超过 $f(n)$ 条指令（$f(n)$ 如上所述）或发送无效指令，裁判将返回"-1"。收到此响应后，你的程序应立即终止以避免被判错误答案。

在打印指令后，请勿忘记换行并刷新输出缓冲区，否则会因空闲超时被判失败。具体操作如下：

• C++：使用 fflush(stdout) 或 cout.flush()；
• Java：使用 System.out.flush()；
• Python：使用 sys.stdout.flush()；
• Rust：使用 std::io::stdout().flush()；
• 其他语言请参考文档。

交互器是非自适应的。未知整数 $x$ 在交互过程中不会改变。

Hack 格式

要进行 hack，请使用以下格式：

第一行包含一个整数 $t$（$1 \leq t \leq 5000$）——测试用例数量。

每个测试用例的第一行包含两个正整数 $n$ 和 $x$（$1 \leq n,x \leq 10^9$）——分别表示目标值和未知整数的初始值。

解释
$\texttt{2}$：共有 2 个测试用例。
$\texttt{100}$：第一个测试用例中，未知整数 $x = 9$，目标值 $n = 100$。
$\texttt{add -10}$ $\texttt{0}$：指令"add -10"返回"0"，因为 $9 + (-10) \le 0$，$x$ 保持为 9。
$\texttt{add 1}$ $\texttt{1}$：指令"add 1"成功，$x$ 变为 10。
$\texttt{mul 10}$ $\texttt{1}$：指令"mul 10"成功，$x$ 变为 100。
$\texttt{!}$ $\texttt{1}$：确认 $x = n$。
$\texttt{5}$：第二个测试用例中，$x = 1234$，$n = 5$。
$\texttt{digit}$ $\texttt{1}$：$x$ 变为各位数字之和 10。
$\texttt{div 2}$ $\texttt{1}$：指令"div 2"成功，$x$ 变为 5。
$\texttt{!}$ $\texttt{1}$：确认 $x = n$。

注意示例中的空行仅为清晰展示，实际交互中不会出现。

翻译由 DeepSeek V3 完成