Задача . D2. ПРС и криминальный список (сложная версия)

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