Дан простой неориентированный граф с $n$ вершинами. Этот граф обладает дополнительным свойством:

• Любой порожденный подграф содержит вершину со степенью не более $k$.

Вам необходимо найти этот скрытый граф. Вы можете проверить для любого подмножества вершин, является ли оно независимым множеством. Если это не так, мы покажем вам ребро, оба конца которого лежат внутри этого подмножества.

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

Вам нужно угадать граф, сделав не более $2nk + n$ запросов.

Протокол взаимодействия

Взаимодействие начинается со строки, содержащей одно целое число $n$: количество вершин в скрытом графе ($2 \le n \le 2000$).

Целое число $k$ не дано, но оно удовлетворяет ограничению $1 \le k < n$, $nk \le 2000$.

После этого вы можете делать запросы.

Чтобы сделать запрос, выведите одну строку, содержащую «? $k$» ($1 \le k \le n$), а затем $k$ различных целых чисел $v_1, v_2, \dots, v_k$ ($1 \le v_i \le n$). Разделяйте числа пробелами. Затем выполните сброс буфера вывода (flush).

После каждого запроса считайте одну строку с двумя целыми числами $i, j$. Если в порожденном подграфе $v_1, v_2, \dots, v_k$ нет ребер, то $i = j = -1$. В противном случае $i \neq j$, $i \in \{v_1, \dots, v_k\}$, $j \in \{v_1, \dots, v_k\}$, и в графе существует ребро с концами $i$ и $j$.

Когда вы найдете граф, выведите в первой строке «! $m$». Затем выведите $m$ строк, каждая из которых должна содержать описание ребра графа: два целых числа $u, v$ ($1 \le u, v \le n$), обозначающих индексы вершин, соединенных ребром.

Ваше решение получит вердикт Wrong Answer или Time Limit Exceeded, если вы сделаете более $2nk + n$ запросов.

Ваше решение получит вердикт Idleness Limit Exceeded, если вы ничего не выведете или забудете сбросить буфер вывода.

Для сброса буфера вывода (flush) необходимо выполнить следующие действия сразу после вывода запроса и символа переноса строки:

• fflush(stdout) или cout.flush() в C++;
• System.out.flush() в Java;
• flush(output) в Pascal;
• stdout.flush() в Python;
• см. документацию для других языков.

Примеры

Входные данные 1

3
1 2
2 3
1 3

Выходные данные 1

? 2 1 2
? 2 2 3
? 2 1 3
! 3
1 2
2 3
1 3