Это интерактивная задача!
Тимофей пишет соревнование, которое называется Capture the flag (или сокращённо CTF). Ему осталась одна задача, в которой нужно взломать систему безопасности. Вся система основана на полиномиальных хеш-функциях\(^{\text{∗}}\).
Тимофей может ввести в систему строку, состоящую из строчных латинских букв, и система выдаст её полиномиальный хеш. Чтобы взломать систему, Тимофею нужно узнать параметры полиномиального хеша, которые использует система (\(p\) и \(m\)).
У Тимофея осталось очень мало времени, поэтому он успеет сделать только \(3\) запроса. Помогите ему решить задачу.
Протокол взаимодействия
Чтобы сделать запрос в систему выведите ? \(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;
- смотрите документацию для других языков.
Примечание
Ответом на первый запрос будет \((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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1
32
28
|
? aa
? yb
! 31 59
|