Tu tarea consiste en seleccionar $N$ puntos en el plano de coordenadas y dibujar $M$ segmentos rectos que los conecten, de tal manera que haya exactamente $K$ caras finitas. Aquí, las caras son las regiones en las que el plano es dividido por los segmentos. Una de las regiones es infinita y debe ser ignorada.

Más formalmente, tu configuración debe satisfacer las siguientes condiciones:

• Las coordenadas $x$ e $y$ de cada punto deben ser números enteros del 1 al 79.
• Todos los puntos deben tener posiciones diferentes.
• No debe haber múltiples segmentos de línea conectando dos puntos.
• Dos segmentos de línea diferentes no deben intersectarse excepto en un punto extremo.
• Los puntos distintos a los extremos del segmento no deben estar sobre el segmento.

En la figura a continuación, (a) es un caso en el que se crea una cara con 3 puntos y 3 segmentos de línea. (b) es un caso en el que se crean 3 caras con 4 puntos y 6 segmentos de línea. (c) es una salida incorrecta porque hay curvas, y (d) es incorrecta porque hay segmentos de línea que se intersectan.

Entrada

En la primera línea, hay tres números enteros positivos, $N$, $M$ y $K$, que representan el número de puntos, el número de segmentos y el número de caras a crear, respectivamente ($3 \le N \le 3000$, $0 \le M$, $0 \le K$).

Se garantiza que, para los $N$, $M$ y $K$ dados, existe una solución.

Salida

En las primeras $N$ líneas, imprime las coordenadas de los puntos seleccionados. La $i$-ésima de esas líneas debe contener dos enteros $x_i$ e $y_i$ ($1 \le x_i, y_i \le 79$): las coordenadas del $i$-ésimo punto.

Luego, imprime $M$ líneas describiendo los segmentos. Cada una de estas líneas debe contener dos enteros entre 1 y $N$: los índices de los puntos conectados por un segmento.

Si hay más de una solución posible, imprime cualquiera de ellas.

Ejemplos

Entrada 1

4 6 3

Salida 1

1 1
3 1
2 2
2 3
1 2
1 3
1 4
2 3
2 4
3 4

Entrada 2

6 5 1

Salida 2

1 1
1 2
2 1
3 1
3 2
4 1
1 2
1 3
2 3
4 5
5 6

Nota

La imagen de la izquierda muestra 3 caras hechas con 4 puntos y 6 segmentos de línea. La imagen de la derecha muestra 1 cara hecha con 6 puntos y 5 segmentos de línea.