Description:
Это интерактивная задача.
Когда данных становится слишком много и они не помещаются на один сервер, их приходится шардировать. Рассмотрим систему хранения постов пользователей, которая расположена на $$$S$$$ серверах, нумеруемых с единицы. Каждый раз когда пользователь пишет пост, ему выдается уникальный идентификатор в пределах от 1 до $$$10^{18}$$$ и сохраняется на случайный сервер. Чем позже был создан пост, тем больше его $$$id$$$. Иногда посты удаляются, поэтому на серверах может лежать существенно разное количество постов.
Рассмотрим все неудаленные $$$id$$$ постов пользователя и отсортируем их по возрастанию. Вам хочется узнать $$$k$$$-й из них. Для этого вы можете послать не более 100 дополнительных запросов. Каждый запрос имеет формат «? $$$i$$$ $$$j$$$». В ответ вы получите идентификатор $$$j$$$-го по возрастанию поста пользователя среди хранящихся на $$$i$$$-м сервере. Когда вы считаете, что знаете $$$k$$$-й по возрастанию идентификатор, вместо запроса необходимо вывести ответ в формате «! $$$id$$$».
Input Format:
None
Output Format:
None
Note:
В примере на первом сервере хранятся посты с $$$id$$$ 1, 3 и 10. А на втором 5 и 7. Необходимо найти третье по возрастанию число, это 5.