C3. Взлом чисел (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. В этой версии ограничение на количество команд описано в условии. Вы можете делать взломы только если все версии задачи решены.

Это интерактивная задача.

Добро пожаловать, Дуэлянты! В этой интерактивной задаче есть неизвестное целое число $$$x$$$ ($$$1 \le x \le 10^9$$$). Вы должны сделать его равным заданному на входе целому числу $$$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$$$если $$$x$$$ делится на $$$y$$$$$$x \leftarrow \mathrm{res}$$$"1"
иначе$$$x \leftarrow x$$$"0"
"digit" —$$$\mathrm{res} = S(x)$$$$$$^{\text{∗}}$$$ —$$$x \leftarrow \mathrm{res}$$$"1"

Пусть $$$f(n)$$$ — минимальное целое число, такое, что существует последовательность из $$$f(n)$$$ команд, которая преобразует $$$x$$$ в $$$n$$$ для всех $$$x$$$ ($$$1 \le x \le 10^9$$$). Вы не знаете значение $$$x$$$ заранее. Найдите $$$f(n)$$$ такое, что, независимо от значения $$$x$$$, вы всегда сможете преобразовать его в $$$n$$$, используя не более $$$f(n)$$$ команд.

Вы должны сделать $$$x$$$ равным $$$n$$$, используя не более $$$f(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$$$": прибавить некоторое целое число $$$y$$$ ($$$-10^{18} \le y \le 10^{18}$$$) к $$$x$$$.

    Жюри выведет "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". После получения такого ответа ваша программа должна немедленно завершиться, чтобы получить вердикт Неправильный ответ. В противном случае она может получить любой другой вердикт.

После вывода каждой команды не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».

Интерактор неадаптивен. Неизвестное целое число $$$x$$$ не меняется в процессе взаимодействия.

Взломы

Чтобы сделать взлом, используйте следующий формат.

Первая строка должна содержать одно целое число $$$t$$$ ($$$1 \leq t \leq 5000$$$) — количество тестов.

Единственная строка каждого набора входных данных должна содержать два целых положительных числа $$$n$$$ и $$$x$$$ ($$$1 \leq n,x \leq 10^9$$$) — неизвестное целое число и целевое значение, к которому оно должно быть приведено.

$$$^{\text{∗}}$$$Чтобы сбросить буфер вывода, используйте:

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
  • смотрите документацию для других языков.
Пример
Входные данные
2
100

0

1

1

1

5

1

1

1
Выходные данные

add -10

add 1

mul 10

!

digit

div 2

!
Примечание
РешениеЖюриОбъяснение
$$$\texttt{2}$$$2 набора входных данных.
$$$\texttt{100}$$$В первом наборе входных данных неизвестное целое число $$$x = 9$$$, и мы должны сделать его равным $$$n = 100$$$.
$$$\texttt{add -10}$$$$$$\texttt{0}$$$Ответ на "add -10" равен "0". Это означает, что команда сложения не была успешной, так как $$$x + y = 9 + (-10) \le 0$$$, и $$$x$$$ остается $$$9$$$ после команды
$$$\texttt{add 1}$$$$$$\texttt{1}$$$Ответ на "add 1" равен "1". Это означает, что команда сложения была успешной, так как $$$x + y = 9 + 1 = 10$$$, и $$$x$$$ изменяется на $$$10$$$ после команды.
$$$\texttt{mul 10}$$$$$$\texttt{1}$$$Ответ на "mul 10" равен "1". Это означает, что команда умножения была успешной, так как $$$x \cdot y = 10 \cdot 10 = 100$$$, и $$$x$$$ изменяется на $$$100$$$ после команды.
$$$\texttt{!}$$$$$$\texttt{1}$$$Ответ на "!" равен "1". Это означает, что вы определили, что $$$x$$$ равно $$$n$$$.
$$$\texttt{5}$$$Во втором наборе входных данных неизвестное целое число $$$x = 1234$$$, и мы должны сделать его равным $$$n = 5$$$.
$$$\texttt{digit}$$$$$$\texttt{1}$$$Ответ на "digit" равен "1". Это означает, что $$$x$$$ стал равным сумме его цифр $$$1 + 2 + 3 + 4 = 10$$$, и $$$x$$$ изменяется на $$$10$$$ после команды.
$$$\texttt{div 2}$$$$$$\texttt{1}$$$Ответ на "div 2" равен "1". Это означает, что команда деления была успешной, так как $$$y = 2$$$ является делителем $$$x = 10$$$, и $$$x$$$ изменяется на $$$\frac{x}{y} = \frac{10}{2} = 5$$$ после команды.
$$$\texttt{!}$$$$$$\texttt{1}$$$Ответ на "!" равен "1". Это означает, что вы определили, что $$$x$$$ равно $$$n$$$.

Обратите внимание, что пустые строки в примерах ввода и вывода приведены для ясности и не встречаются в реальном взаимодействии.