Dany jest prosty graf nieskierowany o $n$ wierzchołkach. Graf ten posiada dodatkową własność:

• Każdy podgraf indukowany zawiera wierzchołek o stopniu co najwyżej $k$.

Musisz odnaleźć ten ukryty graf. Możesz sprawdzić dla dowolnego podzbioru, czy jest on zbiorem niezależnym. Jeśli nie jest, pokażemy Ci krawędź, której oba końce znajdują się wewnątrz tego zbioru.

Nie zmieniamy grafu w trakcie interakcji, więc możesz założyć, że jest on ustalony. Możemy jednak wybrać dowolną krawędź wewnątrz podgrafu indukowanego, którą Ci pokażemy. Innymi słowy, we wszystkich testach graf jest ustalony, ale interaktor jest adaptacyjny.

Musisz odgadnąć graf w co najwyżej $2nk + n$ zapytaniach.

Interakcja

Interakcja rozpoczyna się od wczytania jednej linii zawierającej liczbę całkowitą $n$: liczbę wierzchołków w ukrytym grafie ($2 \le n \le 2000$).

Liczba całkowita $k$ nie jest podana, ale spełnia warunek $1 \le k < n$ oraz $nk \le 2000$.

Następnie możesz wykonywać zapytania.

Aby wykonać zapytanie, wypisz jedną linię zawierającą "? $k$" ($1 \le k \le n$), a następnie $k$ różnych liczb całkowitych $v_1, v_2, \dots, v_k$ ($1 \le v_i \le n$). Kolejne liczby oddziel spacjami. Następnie opróżnij bufor wyjściowy (flush).

Po każdym zapytaniu wczytaj jedną linię z dwiema liczbami całkowitymi $i, j$. Jeśli w podgrafie indukowanym przez $v_1, v_2, \dots, v_k$ nie ma krawędzi, to $i = j = -1$. W przeciwnym razie $i \neq j$, $i \in \{v_1, \dots, v_k\}$, $j \in \{v_1, \dots, v_k\}$, a krawędź o końcach $i$ oraz $j$ istnieje w grafie.

Gdy odnajdziesz graf, w pierwszej linii wypisz "! $m$". Następnie w kolejnych $m$ liniach wypisz opis krawędzi grafu; każda z nich powinna zawierać dwie liczby całkowite $u, v$ ($1 \le u, v \le n$), oznaczające indeksy wierzchołków połączonych krawędzią.

Twoje rozwiązanie otrzyma werdykt Wrong Answer lub Time Limit Exceeded, jeśli wykonasz więcej niż $2nk + n$ zapytań.

Twoje rozwiązanie otrzyma werdykt Idleness Limit Exceeded, jeśli nic nie wypiszesz lub zapomnisz opróżnić bufor wyjściowy.

Aby opróżnić bufor (flush), musisz wykonać następujące czynności bezpośrednio po wypisaniu zapytania i znaku nowej linii:

• fflush(stdout) lub cout.flush() w C++;
• System.out.flush() w Javie;
• flush(output) w Pascalu;
• stdout.flush() w Pythonie;
• sprawdź dokumentację dla innych języków.

Przykład

Wejście 1

3
1 2
2 3
-1 -1

Wyjście 1

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