Votre tâche consiste à sélectionner $N$ points sur le plan cartésien et à tracer $M$ segments de droite les reliant de telle sorte qu'il y ait exactement $K$ faces finies. Ici, les faces sont les régions dans lesquelles le plan est divisé par les segments. L'une des régions est infinie et doit être ignorée.

Plus formellement, votre configuration doit satisfaire les conditions suivantes :

• Les coordonnées $x$ et $y$ de chaque point doivent être des entiers compris entre 1 et 79.
• Tous les points doivent avoir des positions distinctes.
• Il ne doit pas y avoir plusieurs segments de droite reliant deux points.
• Deux segments de droite différents ne doivent pas s'intersecter, sauf à une extrémité.
• Les points autres que les extrémités du segment ne doivent pas se trouver sur le segment.

Dans la figure ci-dessous, (a) est un cas où une face est créée avec 3 points et 3 segments de droite. (b) est un cas où 3 faces sont créées avec 4 points et 6 segments de droite. (c) est une sortie incorrecte car il y a des courbes, et (d) est incorrect car il y a des segments de droite qui s'intersectent.

Entrée

Sur la première ligne, il y a trois entiers positifs $N$, $M$ et $K$, représentant respectivement le nombre de points, le nombre de segments et le nombre de faces à créer ($3 \le N \le 3000$, $0 \le M$, $0 \le K$).

Il est garanti que, pour les $N$, $M$ et $K$ donnés, une solution existe.

Sortie

Sur les $N$ premières lignes, imprimez les coordonnées des points sélectionnés. La $i$-ième de ces lignes doit contenir deux entiers $x_i$ et $y_i$ ($1 \le x_i, y_i \le 79$) : les coordonnées du $i$-ième point.

Ensuite, imprimez $M$ lignes décrivant les segments. Chacune de ces lignes doit contenir deux entiers compris entre 1 et $N$ : les indices des points reliés par un segment.

S'il existe plus d'une solution possible, imprimez-en n'importe laquelle.

Exemples

Entrée 1

4 6 3

Sortie 1

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

Entrée 2

6 5 1

Sortie 2

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

Remarque

L'image de gauche montre 3 faces créées avec 4 points et 6 segments de droite. L'image de droite montre 1 face créée avec 6 points et 5 segments de droite.