Hiperzegar

Limit pamięci: 32 MB

Smerf Ważniak stwierdził, że dni są dla niego zbyt krótkie i nie zdąży przez to napisać wszystkich tomów Złotych myśli Smerfa Ważniaka. Postanowił więc udać się do Ojca Czasu i nakłonić go, aby ten wydłużył dobę do 48 godzin. Ojciec Czas początkowo nie chciał przystać na tę propozycję, ale namolny smerf nie dawał za wygraną i w końcu staruszek się zgodził. Postawił jednak jeden warunek: Ważniak ma rozwiązać zagadkę Hiperzegara.

Hiperzegar składa się z zegarów. Każdy z nich ma jedną wskazówkę i kilka liczb na tarczy. Na tarczy -tego zegara (dla ) znajdują się liczby od do . Początkowo na wszystkich zegarach wskazówki pokazują liczbę . Tak Ojciec Czas objaśniał zagadkę Hiperzegara smerfowi:

Masz wykonać serię ruchów. Każdy ruch polega na przesunięciu wskazówki dowolnie wybranego zegara o jedną liczbę w lewo lub w prawo. Po ostatnim ruchu wskazówki Hiperzegara muszą wrócić do pierwotnego położenia. Ponadto, w wyniku przesuwania wskazówek, każda możliwa konfiguracja Hiperzegara musi pojawić się dokładnie raz.

Ważniak już godzinę majstruje coś przy Hiperzegarze i jest coraz bardziej przekonany, że pomimo całej swej mądrości nie będzie umiał rozwiązać jego zagadki. Pomóż biednemu smerfowi!

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą dodatnią . W kolejnych wierszach znajduje się po jednej liczbie całkowitej większej niż : w -szym wierszu znajduje się liczba . Liczba wszystkich możliwych konfiguracji zegara (czyli ) jest nie większa niż .

Wyjście

Jeśli zagadka Hiperzegara nie posiada rozwiązania, należy wypisać jedno słowo NIE. W przeciwnym przypadku należy wypisać wierszy - opisy kolejnych ruchów. Każdy z nich powinien zawierać dwie liczby całkowite. Pierwsza liczba () oznacza numer zegara, którego wskazówkę się przesuwa. Druga liczba oznacza, w którą stronę przesuwamy wskazówkę: (jeśli w prawo) lub (jeśli w lewo). Możliwe są różne poprawne odpowiedzi, Twój program ma wypisać dowolną z nich.

Przykład

Dla danych wejściowych:

3
2
2
3

poprawną odpowiedzią jest:

1 1
2 1
1 -1
3 1
1 1
2 -1
3 1
2 1
1 -1
2 -1
3 -1
3 -1

Autor zadania: Jakub Pawlewicz (treść: Tomasz Idziaszek).