Dawno temu żyło dziecko o imieniu Kino, które bardzo lubiło podróżować i odwiedziło wiele niezwykłych miejsc. Pewnego dnia dotarło do wielkiego mostu i zauważyło stojące na nim liczne kabriolety. Niestety most był tak wąski, że mieścił się na nim tylko jeden samochód na szerokość, a kierowcy nie ustępowali sobie drogi. W rezultacie samochody nadjeżdżające z obu stron utknęły w korku.
Później budowniczy dodał mostowi nową funkcję: obrót wybranego fragmentu o $180$ stopni, który odwracał znajdujące się na nim kabriolety, jak pokazano poniżej:
Rysunek 1. Kabriolety 321 po obrocie tworzą 123.
Jak pokazano na rysunku, spotkanie kabrioletów 321 z kabrioletami 45 na moście spowodowało korek. Możemy wtedy obrócić fragment z samochodami 321, otrzymując kolejność 12345, przy czym wszystkie samochody będą skierowane w tę samą stronę. Dzięki temu mogą zjechać z mostu. To oczywiście tylko prosty przykład: na prawdziwym moście sytuacja jest znacznie bardziej złożona i osiągnięcie postaci 12345 wymaga wielu obrotów.
Jednak po zaprojektowaniu mostu jego projektant również wyruszył w podróż, a nikt z pozostałych mieszkańców nie umiał obsługiwać tego niezwykłego mostu. Ruch stawał się więc coraz bardziej chaotyczny, aż w końcu powstała obecna sytuacja. Aby przejść przez most, Kino znalazł przy nim urządzenie sterujące i instrukcję, dzięki czemu ponownie odkrył sposób obsługi mostu. Z pomocą okolicznych mieszkańców udało mu się ustawić kabriolety w kolejności $1,2,3,\ldots$, wszystkie skierowane w tę samą stronę. Czy wiesz, jak to zrobił?
Wejście
Jest to zadanie, w którym należy przesłać jedynie odpowiedzi. Pliki wejściowe convertible1.in do convertible10.in znajdują się już w katalogu użytkownika. Pierwszy wiersz pliku wejściowego zawiera liczbę kabrioletów na moście $n$. Kabriolety są ponumerowane od $1$ do $n$. Drugi wiersz opisuje położenia i kierunki kabrioletów za pomocą ciągu wartości $+i$ lub $-i$. Wartość $-i$ na pozycji $j$ oznacza, że na pozycji $j$ mostu znajduje się kabriolet $i$ skierowany w prawo. Wartość $+i$ na pozycji $j$ oznacza kabriolet $i$ skierowany w lewo.
Wyjście
Pliki wyjściowe convertible1.out do convertible10.out należy umieścić w katalogu użytkownika; nie trzeba przesyłać programu. Pierwszy wiersz pliku wyjściowego zawiera liczbę obrotów $m$. Każdy z następnych $m$ wierszy opisuje jeden obrót, podając pozycję lewego i prawego końca obracanego fragmentu. Twój wynik musi zapewniać, że końcowy ciąg to $1,2,3,\ldots,n$, a nie $-1,-2,-3,\ldots,-n$ ani żaden inny.
Przykład
Wejście 1
5 -3 -2 -1 4 5
Wyjście 1
1 1 3
Podzadania
Za każdy test można otrzymać maksymalnie 10 punktów. Wynik zależy od stosunku jakości twojego wyniku do jakości odpowiedzi wzorcowej.
Jak testować program
Do zadania dołączono program sprawdzający dane wyjściowe convertible_c. Uruchamia się go następująco:
#./convertible_c 3
To polecenie sprawdza poprawność pliku convertible3.out.