Twoim zadaniem jest wybranie $N$ punktów na płaszczyźnie współrzędnych i narysowanie $M$ prostych odcinków łączących je w taki sposób, aby powstało dokładnie $K$ skończonych ścian. Ściany to obszary, na które płaszczyzna jest dzielona przez odcinki. Jeden z obszarów jest nieskończony i należy go pominąć.

Formalnie, Twoja konfiguracja musi spełniać następujące warunki:

• Współrzędne $x$ oraz $y$ każdego punktu muszą być liczbami całkowitymi z zakresu od 1 do 79.
• Wszystkie punkty muszą znajdować się w różnych miejscach.
• Nie może istnieć więcej niż jeden odcinek łączący dwa punkty.
• Dwa różne odcinki nie mogą przecinać się w żadnym punkcie poza końcami odcinków.
• Punkty inne niż końce odcinka nie mogą leżeć na tym odcinku.

Na poniższym rysunku (a) przedstawia przypadek, w którym jedna ściana jest utworzona przez 3 punkty i 3 odcinki. (b) przedstawia przypadek, w którym 3 ściany są utworzone przez 4 punkty i 6 odcinków. (c) jest niepoprawnym wynikiem, ponieważ zawiera krzywe, a (d) jest niepoprawny, ponieważ zawiera przecinające się odcinki.

Wejście

W pierwszej linii znajdują się trzy liczby całkowite dodatnie $N$, $M$ oraz $K$, oznaczające odpowiednio liczbę punktów, liczbę odcinków oraz liczbę ścian, które mają zostać utworzone ($3 \le N \le 3000$, $0 \le M$, $0 \le K$).

Gwarantuje się, że dla podanych $N$, $M$ oraz $K$ rozwiązanie istnieje.

Wyjście

W pierwszych $N$ liniach wypisz współrzędne wybranych punktów. $i$-ta z tych linii musi zawierać dwie liczby całkowite $x_i$ oraz $y_i$ ($1 \le x_i, y_i \le 79$): współrzędne $i$-tego punktu.

Następnie wypisz $M$ linii opisujących odcinki. Każda z tych linii musi zawierać dwie liczby całkowite z zakresu od 1 do $N$: indeksy punktów połączonych odcinkiem.

Jeśli istnieje więcej niż jedno możliwe rozwiązanie, wypisz dowolne z nich.

Przykład

Wejście 1

4 6 3

Wyjście 1

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

Wejście 2

6 5 1

Wyjście 2

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

Uwagi

Lewy rysunek przedstawia 3 ściany utworzone przez 4 punkty i 6 odcinków. Prawy rysunek przedstawia 1 ścianę utworzoną przez 6 punktów i 5 odcinków.