D2. ПРС и криминальный список (сложная версия)
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это сложная версия задачи. Единственное различие между простой и сложной версиями заключается в том, что здесь $$$2\leq k\leq 100$$$. Вы можете делать взломы, только если решили обе версии этой задачи.

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

Для каждого десятичного числа есть эквивалентное ему $$$k$$$-ичное. Цифры числа, записанного в $$$k$$$-ичной системе счисления, будем называть $$$k$$$-цифрами. Определим $$$k$$$-ичный XOR двух $$$k$$$-цифр $$$a$$$ и $$$b$$$ как $$$(a + b)\bmod k$$$.

$$$k$$$-ичный XOR двух $$$k$$$-ичных чисел равен новому числу, полученному из первых двух попарным $$$k$$$-ичным XOR соответствующих $$$k$$$-цифр. $$$k$$$-ичный XOR двух десятичных чисел $$$a$$$ и $$$b$$$ обозначается $$$a\oplus_{k} b$$$ и равен десятичному представлению $$$k$$$-ичного XOR $$$a$$$ и $$$b$$$, записанных в $$$k$$$-ичной системе счисления. Все числа, встречающиеся далее в условии, записаны в десятичной системе счисления, если не указано иное.

Вы взломали базу преступлений Полиции Рокпорт-Сити (ПРС), так же известную как Криминальный Список. Но, чтобы получить к ней доступ, вам нужен пароль. Вы его не знаете, но вполне уверены, что его значение лежит между $$$0$$$ и $$$n-1$$$ включительно. Вы решили угадать его. Вы можете сделать не более чем $$$n$$$ попыток, далее система заблокируется. Система адаптивна – каждый раз, когда вы делаете неверную попытку, она меняет пароль. А именно, если до попытки пароль был равен $$$x$$$ и вы попытались ввести другое число $$$y$$$, то система поменяет пароль на число $$$z$$$ такое, что $$$x\oplus_{k} z=y$$$. Угадайте пароль и взломайте систему.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1\leq t\leq 10\,000$$$) — количество наборов входных данных. Далее следует описание $$$t$$$ наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$) и $$$k$$$ $$$(2\leq k\leq 100)$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

Протокол взаимодействия

Для каждого набора входных данных считайте два целых числа $$$n$$$ и $$$k$$$. Вам разрешено сделать не более $$$n$$$ попыток угадать пароль.

Для каждой попытки выведите одно целое число $$$y$$$ ($$$0\leq y\leq 2\cdot 10^7$$$). Пусть текущий пароль равен $$$x$$$. Считайте одно целое число $$$r$$$.

Если $$$x=y$$$, вы считаете $$$r=1$$$, и этот набор входных данных считается решенным. Далее вы должны продолжить решать оставшиеся наборы.

Иначе вы считаете $$$r=0$$$, и система поменяет пароль на число $$$z$$$ такое, что $$$x\oplus_{k} z=y$$$.

После каждой попытки не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:

  • fflush(stdout) или cout.flush() в C++;
  • System.out.flush() в Java;
  • flush(output) в Pascal;
  • stdout.flush() в Python;
  • смотрите документацию для других языков.

Если вы сделаете некорректную попытку или превысите лимит в $$$n$$$ попыток, вы считаете $$$r=-1$$$ вместо ответа и получите вердикт Неправильный ответ. В таком случае ваша программа должна немедленно завершается, чтобы избежать неопределенных вердиктов.

Обратите внимание, что система адаптивна. Это значит, что изначальный пароль не зафиксирован в начале и может зависеть от ваших запросов. Гарантируется, что в любой момент времени существует хотя бы один начальный пароль, для которого согласуются все ответы на запросы.

Взломы:

Для взломов используйте следующий формат:

Первая строка должна содержать одно целое число $$$t$$$ ($$$1\leq t\leq 10\,000$$$) — количество наборов входных данных.

Первая и единственная строка каждого набора должна содержать два целых числа $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$) и $$$k$$$ ($$$2\leq k\leq 100$$$), равные соответственно количеству возможных попыток и основанию системы счисления. Оптимальный начальный пароль будет автоматически подобран системой.

Сумма $$$n$$$ по всем наборам входных данных не должна превышать $$$2\cdot 10^5$$$.

Пример
Входные данные
2
5 2

0

0

1
5 3

0

0

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

4

5


1

4

6

Примечание

Набор 1:

В этом наборе входных данных загаданный пароль равен $$$2$$$.

Первая попытка равна $$$3$$$. Это не равно текущему паролю. Поэтому система возвращает ответ $$$0$$$ и меняет пароль на $$$1$$$, поскольку $$$2\oplus_2 1=3$$$.

Вторая попытка равна $$$4$$$. Это не равно текущему паролю. Поэтому система возвращает ответ $$$0$$$ и меняет пароль на $$$5$$$, поскольку $$$1\oplus_2 5=4$$$.

Третья попытка равна $$$5$$$. Это равно текущему паролю. Поэтому система возвращает ответ $$$1$$$ и работа сделана.

Набор 2:

В этом наборе входных данных загаданный пароль равен $$$3$$$.

Первая попытка равна $$$1$$$. Это не равно текущему паролю. Поэтому система возвращает $$$0$$$ и меняет пароль на $$$7$$$, поскольку $$$3\oplus_3 7=1$$$. $$$[3=(10)_3$$$, $$$7=(21)_3$$$, $$$1=(01)_3$$$ и $$$(10)_3\oplus_3 (21)_3 = (01)_3]$$$.

Вторая попытка равна $$$4$$$. Это не равно текущему паролю. Поэтому система возвращает $$$0$$$ и меняет пароль на $$$6$$$, поскольку $$$7\oplus_3 6=4$$$. $$$[7=(21)_3$$$, $$$6=(20)_3$$$, $$$4=(11)_3$$$ and $$$(21)_3\oplus_3 (20)_3 = (11)_3]$$$.

Третья попытка равна $$$6$$$. Это равно текущему паролю. Поэтому система возвращает ответ $$$1$$$ и работа сделана.

Заметьте, что начальные пароли были взяты такими для наглядности объяснения. В действительности система может повести себя иначе, поскольку она адаптивна.