Это интерактивная задача.
Загадано некоторое положительное целое число \(1 \le x \le 10^9\).
За один запрос вы можете выбрать два положительных целых числа \(a \neq b\). В качестве ответа на этот запрос вы получите \(\gcd(x + a, x + b)\), где \(\gcd(n, m)\) обозначает наибольший общий делитель чисел \(n\) и \(m\).
Чтобы угадать одно загаданное число \(x\), вы можете совершить не более \(30\) запросов.
Протокол взаимодействия
Загаданное число \(x\) зафиксировано до начала взаимодействия и не зависит от ваших запросов.
Для угадывания каждого \(x\) вы можете сделать не более \(30\) запросов следующего вида:
- «? a b» (\(1 \le a, b \le 2 \cdot 10^9\), \(a \neq b\)).
В ответ на этот запрос вы получите \(\gcd(x + a, x + b)\).
Когда вы узнаете число \(x\), выведите одну строку следующего формата:
- «! x» (\(1 \le x \le 10^9\)).
После этого переходите к решению следующего набора входных данных.
Если вы сделаете более \(30\) запросов для одного \(x\), или запросы будут некорректными, взаимодействие будет немедленно прекращено, а ваша программа получит вердикт Неправильный ответ.
После вывода запросов не забудьте выводить символ перевода строки и сбрасывать буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы
Для взломов используйте следующий формат:
Первая строка должна содержать одно целое число \(t\) (\(1 \le t \le 1000\)) — количество наборов входных данных.
Первая и единственная строка каждого набора входных данных должна содержать единственное целое число \(x\) (\(1 \le x \le 10^9\)) — число \(x\), которое нужно угадать.
Примечание
Первое загаданное число равно \(4\), поэтому ответы на запрос следующие:
«? 1 2» — \(\gcd(4 + 1, 4 + 2) = \gcd(5, 6) = 1\).
«? 12 4» — \(\gcd(4 + 12, 4 + 4) = \gcd(16, 8) = 8\).
Второе загаданное число равно \(10^9\), поэтому ответ на запрос следующий:
«? 2000000000 1999999999» — \(\gcd(3 \cdot 10^9, 3 \cdot 10^9 - 1) = 1\).
Эти запросы показаны только для лучшего понимания протокола взаимодействия, и их недостаточно, чтобы однозначно восстановить \(x\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1
8
1
|
? 1 2
? 12 4
! 4
? 2000000000 1999999999
! 1000000000
|