Это интерактивная задача.
Алиса, Витя, Сева и Антон решили перемешать колоду карт. Для этого они позвали \(n\) своих друзей, усадили их по кругу, пронумеровали от \(1\) до \(n\) против часовой стрелки (то есть друзья \(i\) и \(i+1\) являются соседями, друзья \(1\) и \(n\) тоже соседи) и раздали каждому по \(k\) карт, где \(k\) — четно. Соседом слева человека \(i\) является человек \(i - 1\), а соседом справа — человек \(i + 1\) (за исключением людей \(1\) и \(n\), которые являются соответствующими соседями друг друга).
Каждую секунду происходит следующее: если у человека находится \(x\) карт, то он передаёт \(\lfloor x / 2 \rfloor\) карт своему соседу слева и \(\lceil x / 2 \rceil\) карт соседу справа. Передача карт происходит одновременно для всех игроков.
Оказалось, что человек под номером \(p\) не понял, что он должен делать, и каждую секунду отдаёт все свои карты своему соседу справа. Вы знаете общее число друзей \(n\) и начальное количество карт у каждого из них \(k\), но не знаете \(p\). Ваша задача — узнать \(p\), задавая вопросы вида «сколько карт в данный момент находится у участника с номером \(q\)?», где \(q\) — некоторый выбранный вами индекс. После каждого из ваших вопросов участники произведут ровно один ход, передав карты своим соседям. Вам нужно угадать искомую позицию, задав не более \(1000\) вопросов.
Протокол взаимодействия
Для того, чтобы узнать количество карт в текущий момент у человека под номером \(q\) (\(1 \le q \le n\)), выведите в отдельной строке «? \(q\)». Процесс перемешивания начинается после вашего первого вопроса, таким образом, ответ на первый вопрос всегда в точности равен \(k\).
Когда вы определили человека, который не понял правила, выведите в отдельной строке «! \(p\)», где \(p\) — искомая позиция (\(1 \le p \le n\)), и после этого ваша программа должна немедленно завершиться.
Вам требуется найти искомого человека, задав не более, чем \(1000\) вопросов.
После вывода запроса не забудьте вывести перевод строки и сбросить буфер вывода. В противном случае вы получите вердикт Решение «зависло». Для сброса буфера используйте:
- fflush(stdout) или cout.flush() в C++;
- System.out.flush() в Java;
- flush(output) в Pascal;
- stdout.flush() в Python;
- смотрите документацию для других языков.
Взломы
Для того, чтобы сделать взлом, используйте следующий формат теста.
В единственной строке входных данных должны содержаться три числа \(n\), \(k\) и \(p\) (\(4 \le n \le 10^5\), \(2 \le k \le 10^9\), \(k\) четно, \(1 \le p \le n\)) — количество людей, количество карт у каждого из них и искомая позиция.
Примечание
В примере карты передаются следующим образом:
- \(2\) \(2\) \(2\) \(2\) — у человека \(1\) количество карт равно \(2\).
- \(1\) \(2\) \(3\) \(2\) — у человека \(1\) количество карт равно \(1\).
После этого количество карт у людей перестаёт меняться.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
2
1
2
3
2
|
? 1
? 1
? 2
? 3
? 4
! 2
|