Это интерактивная задача!
Тимофей пишет соревнование, которое называется 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.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
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$$$.
Название |
---|