Это интерактивная задача!
Тимофей пишет соревнование, которое называется Capture the flag (или сокращённо CTF). Ему осталась одна задача, в которой нужно взломать систему безопасности. Вся система основана на полиномиальных хеш-функциях∗.
Тимофей может ввести в систему строку, состоящую из строчных латинских букв, и система выдаст её полиномиальный хеш. Чтобы взломать систему, Тимофею нужно узнать параметры полиномиального хеша, которые использует система (p и m).
У Тимофея осталось очень мало времени, поэтому он успеет сделать только 3 запроса. Помогите ему решить задачу.
∗ Полиномиальный хеш по основанию p и модулю m строки s, состоящей из строчных латинских букв, длины n — это (ord(s1)⋅p0+ord(s2)⋅p1+ord(s3)⋅p2+…+ord(sn)⋅pn−1)mod. Где за 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.
