Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. Оно применяется начиная с раунда 972. ×

H. Fortnite
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Тимофей пишет соревнование, которое называется Capture the flag (или сокращённо CTF). Ему осталась одна задача, в которой нужно взломать систему безопасности. Вся система основана на полиномиальных хеш-функциях$$$^{\text{∗}}$$$.

Тимофей может ввести в систему строку, состоящую из строчных латинских букв, и система выдаст её полиномиальный хеш. Чтобы взломать систему, Тимофею нужно узнать параметры полиномиального хеша, которые использует система ($$$p$$$ и $$$m$$$).

У Тимофея осталось очень мало времени, поэтому он успеет сделать только $$$3$$$ запроса. Помогите ему решить задачу.

$$$^{\text{∗}}$$$ Полиномиальный хеш по основанию $$$p$$$ и модулю $$$m$$$ строки $$$s$$$, состоящей из строчных латинских букв, длины $$$n$$$ — это $$$(\mathrm{ord}(s_1) \cdot p ^ 0 + \mathrm{ord}(s_2) \cdot p ^ 1 + \mathrm{ord}(s_3) \cdot p ^ 2 + \ldots + \mathrm{ord}(s_n) \cdot p ^ {n - 1}) \bmod m$$$. Где за $$$s_i$$$ обозначен $$$i$$$-й символ строки $$$s$$$, за $$$\mathrm{ord}(\mathrm{chr})$$$ — порядковый номер символа $$$\mathrm{chr}$$$ в английском алфавите, а за $$$x \bmod m$$$ остаток, который даёт $$$x$$$ при делении на $$$m$$$.

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

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

Гарантируется, что $$$p$$$ и $$$m$$$, которые использует система удовлетворяют условиям: $$$26 < p \leq 50$$$ и $$$p + 1 < m \leq 2 \cdot 10^9$$$.

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

Чтобы сделать запрос в систему выведите ? $$$s$$$, где $$$s$$$ — строка, длины не более $$$50$$$, хеш которой вы хотите узнать. В ответ на этот запрос вы получите полиномиальный хеш строки $$$s$$$.

Чтобы вывести ответ, выведите ! $$$p$$$ $$$m$$$, где — $$$p$$$ основание хеша, а $$$m$$$ — модуль. После этого сразу же переходите к следующему набору входных данных.

Вы должны сделать не более $$$3$$$ запросов ?, в противном случае вы получите вердикт Wrong Answer.

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

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

32

28
Выходные данные
? aa

? yb

! 31 59
Примечание

Ответом на первый запрос будет $$$(ord(a) \cdot 31^0 + ord(a) \cdot 31^1) \mod 59 = (1 + 1 \cdot 31) \mod 59 = 32$$$.

Ответом на второй запрос является $$$(ord(y) \cdot 31^0 + ord(b) \cdot 31^1) \mod 59 = (25 + 2 \cdot 31) \mod 59 = 28$$$.