To zadanie z dwoma uruchomieniami. Dla każdego testu twoje rozwiązanie zostanie uruchomione dwukrotnie.

Na lekcji informatyki Алеся i Борис uczą się kryptografii. Postanowili wymyślić własną metodę szyfrowania wiadomości.

Алеся wybiera $k$ różnych liczb całkowitych od $1$ do $n$ i oznacza otrzymany zbiór przez $T$. Chce przekazać zbiór $T$ jako zaszyfrowaną wiadomość osobie o imieniu Борис. W tym celu na podstawie zbioru $T$ utworzy i przekaże inny zbiór $R$, również złożony z liczb całkowitych od $1$ do $n$.

Nie chcą, aby po zaszyfrowaniu rozmiar wiadomości się zmienił, więc $R$ również musi zawierać dokładnie $k$ liczb. Uważają też, że jeśli $T$ i $R$ mają choć jeden wspólny element, ich szyfrowanie nie będzie wystarczająco bezpieczne. Nie może więc istnieć liczba należąca zarówno do $T$, jak i do $R$, czyli zbiory $T$ i $R$ muszą być rozłączne. Zagwarantowano, że $k\le n/2$, dlatego na podstawie zbioru $T$ zawsze można utworzyć co najmniej jeden zbiór $R$.

Gdy Борис otrzyma zaszyfrowaną wiadomość $R$, musi ją odszyfrować i otrzymać pierwotną wiadomość $T$.

Pomóż im opracować i zaimplementować algorytmy szyfrowania oraz odszyfrowywania. Przy pierwszym uruchomieniu twój program będzie pełnił rolę osoby o imieniu Алеся, a przy drugim — osoby o imieniu Борис.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba $a$, równa $1$ lub $2$ — numer uruchomienia twojego programu.

W drugim wierszu znajduje się jedna liczba $m$ — liczba wiadomości ($1\le m\le300\,000$), które twój program ma zaszyfrować przy pierwszym uruchomieniu lub odszyfrować przy drugim.

Następne $2m$ wierszy zawiera opisy $m$ wiadomości, po dwa wiersze na wiadomość.

W pierwszym wierszu opisu wiadomości znajdują się dwie liczby całkowite $n_i$ i $k_i$ ($2\le n_i\le10^9$, $1\le k_i\le300\,000$, $k_i\le\frac{n_i}{2}$). W drugim wierszu znajduje się $k_i$ różnych liczb całkowitych od $1$ do $n_i$, w kolejności rosnącej.

Zagwarantowano, że suma wszystkich wartości $k_i$ w jednym teście nie przekracza $300\,000$.

Jeśli $a=1$, podane liczby są pierwotną wiadomością. Jeśli $a=2$, podane liczby są wynikiem zaszyfrowania pewnej wiadomości przez twój program przy jego pierwszym uruchomieniu.

Wyjście

Program powinien wypisać $m$ wierszy. W $i$-tym wierszu powinno znaleźć się $k_i$ różnych liczb całkowitych od $1$ do $n_i$, w kolejności rosnącej.

Przy pierwszym uruchomieniu dla każdej pierwotnej wiadomości $T_i$ program powinien wypisać zbiór $R_i$, rozłączny z $T_i$.

Przy drugim uruchomieniu dla każdej zaszyfrowanej wiadomości $R_i$ program powinien odtworzyć pierwotną wiadomość $T_i$.

Przykład

Pierwsze uruchomienie

Wejście 1

1
2
2 1
1
5 2
1 4

Wyjście 1

2
2 3

Drugie uruchomienie

Wejście 2

2
2
5 2
2 3
2 1
2

Wyjście 2

1 4
1

Uwagi

Zwróć uwagę, że w przykładzie podano konkretne warianty wyjścia przy pierwszym uruchomieniu i wejścia przy drugim. Jeśli twój program wypisze inny zbiór $R$, wejście przy drugim uruchomieniu też będzie inne.

Ponadto przy drugim uruchomieniu zaszyfrowane wiadomości nie muszą być przekazane programowi uczestnika w tej samej kolejności, w jakiej występowały przy pierwszym uruchomieniu.

Podzadania

Aby określić dodatkowe ograniczenia danych wejściowych, oznaczmy ciąg liczb tworzących zbiór $T_i$ przez $t_1,t_2,\ldots,t_{k_i}$. Liczby te są uporządkowane rosnąco.

Oznaczmy sumę $n_i$ w jednym teście przez $N$.

Oznaczmy sumę $k_i$ w jednym teście przez $K$.