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

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

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