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

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

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

Примечание

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

Шардирование постов

Examples