F. Шардирование постовограничение по времени на тест2 секундыограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный выводЭто интерактивная задача.Когда данных становится слишком много и они не помещаются на один сервер, их приходится шардировать. Рассмотрим систему хранения постов пользователей, которая расположена на S серверах, нумеруемых с единицы. Каждый раз когда пользователь пишет пост, ему выдается уникальный идентификатор в пределах от 1 до 10^{18} и сохраняется на случайный сервер. Чем позже был создан пост, тем больше его id. Иногда посты удаляются, поэтому на серверах может лежать существенно разное количество постов.Рассмотрим все неудаленные id постов пользователя и отсортируем их по возрастанию. Вам хочется узнать k-й из них. Для этого вы можете послать не более 100 дополнительных запросов. Каждый запрос имеет формат «? i j». В ответ вы получите идентификатор j-го по возрастанию поста пользователя среди хранящихся на i-м сервере. Когда вы считаете, что знаете k-й по возрастанию идентификатор, вместо запроса необходимо вывести ответ в формате «! id». Протокол взаимодействияВ первой строке записано два числа n и S (1 \le n \le 100, 1 \le S \le 5) — количество пользователей для которых необходимо независимо решить задачу, а также количество серверов, на которых хранятся посты.Далее необходимо n раз решить задачу. Вначале необходимо считать S чисел a_1, a_2, ... a_S (0 \le a_i; \sum a_i \le 10^5) — количество постов пользователя на каждом сервере. В следующей строке будет задано число k (1 \le k \le \sum a_i ) — идентификатор какого по возрастанию поста необходимо узнать.Далее необходимо совершить не более 100 запросов в формате, который описан в условии.Заметим, что ограничение на количество запросов действует на каждого пользователя отдельно, поэтому при переходе к следующему тесту счетчик вопросов сбрасывается.ПримерВходные данные
1 2
3 2
3

3

5

10Выходные данные
? 1 2

? 2 1

? 1 3

! 5
ПримечаниеВ примере на первом сервере хранятся посты с id 1, 3 и 10. А на втором 5 и 7. Необходимо найти третье по возрастанию число, это 5.
Входные данные
1 2
3 2
3

3

5

10
Выходные данные ? 1 2  ? 2 1  ? 1 3  ! 5 
['*special problem', 'binary search', 'interactive']