Задача . F. Шардирование постов

Это интерактивная задача.

Когда данных становится слишком много и они не помещаются на один сервер, их приходится шардировать. Рассмотрим систему хранения постов пользователей, которая расположена на \(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 запросов в формате, который описан в условии.

Заметим, что ограничение на количество запросов действует на каждого пользователя отдельно, поэтому при переходе к следующему тесту счетчик вопросов сбрасывается.