Este es un problema de doble ejecución. En cada prueba, tu solución se ejecutará dos veces.

En la clase de informática, Алеся y Борис están estudiando criptografía. Han decidido inventar su propio método para cifrar mensajes.

Алеся elige $k$ enteros distintos entre $1$ y $n$ y llama $T$ al conjunto obtenido. Quiere transmitir a Борис el conjunto $T$ como un mensaje cifrado. Para ello, a partir de $T$, construirá y transmitirá a Борис otro conjunto $R$, formado también por enteros entre $1$ y $n$.

No quieren que el tamaño del mensaje cambie al cifrarlo, así que $R$ también debe contener exactamente $k$ números. Además, consideran que, si $T$ y $R$ tienen al menos un elemento en común, el cifrado no será suficientemente seguro. Por tanto, no debe existir ningún número que pertenezca tanto a $T$ como a $R$; es decir, los conjuntos $T$ y $R$ deben ser disjuntos. Se garantiza que $k \le n/2$, por lo que siempre es posible construir al menos un conjunto $R$ a partir de $T$.

Cuando Борис reciba el mensaje cifrado $R$, deberá descifrarlo y obtener el mensaje original $T$.

Ayuda a Алеся y Борис a idear e implementar los algoritmos de cifrado y descifrado. En la primera ejecución, tu programa actuará como Алеся; en la segunda, como Борис.

Entrada

La primera línea contiene un número $a$, igual a $1$ o $2$: el número de ejecución de tu programa.

La segunda línea contiene un número $m$: la cantidad de mensajes ($1 \le m \le 300\,000$) que tu programa debe cifrar en la primera ejecución o descifrar en la segunda.

Las siguientes $2m$ líneas describen los $m$ mensajes, con dos líneas por mensaje.

La primera línea de cada mensaje contiene dos enteros $n_i$ y $k_i$ ($2 \le n_i \le 10^9$, $1 \le k_i \le 300\,000$, $k_i \le \frac{n_i}{2}$). La segunda línea contiene $k_i$ enteros distintos entre $1$ y $n_i$, en orden creciente.

Se garantiza que la suma de todos los valores $k_i$ en una prueba no supera $300\,000$.

Si $a=1$, estos números forman el mensaje original. Si $a=2$, estos números son el resultado de cifrar algún mensaje con tu programa durante su primera ejecución.

Salida

El programa debe imprimir $m$ líneas. La línea $i$ debe contener $k_i$ enteros distintos entre $1$ y $n_i$, en orden creciente.

En la primera ejecución, para cada mensaje original $T_i$, el programa debe imprimir un conjunto $R_i$ disjunto de $T_i$.

En la segunda ejecución, para cada mensaje cifrado $R_i$, el programa debe reconstruir el mensaje original $T_i$.

Ejemplos

Primera ejecución

Entrada 1

1
2
2 1
1
5 2
1 4

Salida 1

2
2 3

Segunda ejecución

Entrada 2

2
2
5 2
2 3
2 1
2

Salida 2

1 4
1

Nota

Ten en cuenta que el ejemplo muestra unas opciones concretas para la salida de la primera ejecución y la entrada de la segunda. Si tu programa imprime otro conjunto $R$, la entrada de la segunda ejecución también será diferente.

Además, en la segunda ejecución, los mensajes cifrados no se entregan necesariamente al programa del participante en el mismo orden que en la primera ejecución.

Subtareas

Para indicar las restricciones adicionales de la entrada, denotamos por $t_1,t_2,\ldots,t_{k_i}$ la secuencia de números que define el conjunto $T_i$. Estos números están en orden creciente.

Denotamos por $N$ la suma de los valores $n_i$ en una prueba.

Denotamos por $K$ la suma de los valores $k_i$ en una prueba.