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).