Это сложная версия задачи. Единственное различие между простой и сложной версиями заключается в том, что здесь $$$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$$$. Угадайте пароль и взломайте систему.

Для каждого набора входных данных считайте два целых числа $$$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$$$.