Diamentowy szyfr

Limit pamięci: 32 MB

Renomowana firma jubilerska zamówiła u Ciebie oprogramowanie zabezpieczające sejfy. Firma produkuje dwa rodzaje sejfów do przechowywania diamentów - jeden z przełącznikami, a drugi z przełącznikami. Aby otworzyć sejf potrzebujesz hasła, które składa się z ciągu cyfr. Opracuj program, który na podstawie hasła wygeneruje sposób ustawienia przełączników. Przełączniki ponumerowano od do , -tej pozycji przyporządkowano wartość . Pojedynczy przełącznik ma 3 stany (Góra, Zero i Dół). Sejf otwiera się jeżeli suma wartości przyporządkowanych przełącznikom ustawionym do góry odjąć suma wartości przyporządkowanych przełącznikom ustawionym na dół równa się wartości hasła.

Zadanie

Opracuj program, który:

• wczyta ze standardowego wejścia hasła do sejfów
• dla każdego hasła wygeneruje ustawienie przełączników,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu zapisano wartość oznaczającą liczbę haseł (). W każdym z następnych wierszy znajduje się jedna liczba bez zer znaczących oznaczająca hasło do sejfu. Połowa testów zawiera wyłącznie hasła odpowiadające sejfom z przełącznikami.

Wyjście

Dla każdego hasła wypisz stan przełączników otwierających sejf w dwóch wierszach. W pierwszym wierszu wypisz liczbę przełączników ustawionych do góry oraz ich numery, w drugim wierszu liczbę przełączników ustawionych w dół oraz ich numery. Wszystkie liczby w obrębie jednego wiersza należy oddzielać pojedynczym znakiem spacji.

Przykład

Dla danych wejściowych:

2
5
10

poprawną odpowiedzią jest:

1 2
2 0 1
2 0 2
0