Este es un problema de solo salida. Tenga en cuenta que aún debe enviar código que imprima la salida, no un archivo de texto.

Una 3-coloración válida de un grafo es una asignación de colores (números) del conjunto $\{1, 2, 3\}$ a cada uno de los $n$ vértices, de tal manera que para cualquier arista $(a, b)$ del grafo, los vértices $a$ y $b$ tengan un color diferente. Existen como máximo $3^n$ tales coloraciones para un grafo con $n$ vértices.

Usted trabaja en una empresa y aspira a convertirse en especialista en la creación de grafos con un número determinado de 3-coloraciones. Un día, se entera de que por la tarde recibirá un pedido para producir un grafo con exactamente $6k$ 3-coloraciones. Usted no conoce el valor exacto de $k$, solo que $1 \le k \le 500$.

Usted no quiere esperar al valor específico de $k$ para comenzar a crear el grafo. Por lo tanto, construye de antemano un grafo con un máximo de 19 vértices. Luego, después de conocer el valor particular de $k$, se le permite añadir como máximo 17 aristas al grafo para obtener el grafo requerido con exactamente $6k$ 3-coloraciones.

¿Puede hacerlo?

Entrada

No hay entrada para este problema.

Salida

Primero, imprima $n$ y $m$ ($1 \le n \le 19$, $1 \le m \le \frac{n(n-1)}{2}$) — el número de vértices y aristas del grafo inicial (el construido de antemano). Luego, imprima $m$ líneas con el formato $(u, v)$ — las aristas del grafo.

A continuación, para cada $k$ desde 1 hasta 500, haga lo siguiente:

Imprima $e$ — el número de aristas que añadirá para este $k$ en particular ($1 \le e \le 17$). Luego, imprima $e$ líneas con el formato $(u, v)$ — las aristas que añadirá a su grafo.

No puede haber bucles (self-loops) y, para cada $k$, todas las $m + e$ aristas que utilice deben ser distintas entre sí. El número de 3-coloraciones del grafo para un $k$ particular debe ser exactamente $6k$.

Ejemplos

Entrada 1

-

Salida 1

3 2
1 2
2 3
1
1 3
0

Nota

La salida de ejemplo se proporciona como una muestra. Contiene la salida para $k = 1, 2$.