Śluzy

Limit pamięci: 96 MB

Lata pracy w inżynierii oprogramowania mogą spowodować ciężkie komplikacje psychiczne. Dlatego też programista Bajtazar postanowił porzucić dotychczasowe zajęcie i zaczął się przyglądać losowym ofertom zatrudnienia. Najbardziej zainteresowała go oferta pracy na farmie trudniącej się hodowlą ryb. "Fajna sprawa" - pomyślał Bajtazar - "i w sumie rybki to całkiem przyjemne stworzonka". Bajtazar zaaplikował o interesującą go posadę i przeszedł pozytywnie proces rekrutacji, a dzisiaj po raz pierwszy przyszedł do nowej pracy.

Nowy szef już zdążył przydzielić Bajtazarowi pierwsze zadanie. Musi on odizolować jeden zbiornik wodny od drugiego. Bajtazar przyjrzał się już sposobowi, w jaki zbiorniki są połączone, i oto co wywnioskował.

Dwa zbiorniki wodne są połączone pewną liczbą kanałów. Na każdym kanale znajdują się dwie śluzy. Kanał jest otwarty wtedy i tylko wtedy, gdy znajdujące się na nim śluzy są obie otwarte. Śluzy można otwierać i zamykać za pomocą przełączników. Jeden przełącznik może być podłączony do wielu śluz, ale jedna śluza jest zawsze podłączona do dokładnie jednego przełącznika. Może się tak zdarzyć, że dwie śluzy znajdujące się na jednym kanale są podłączone do jednego przełącznika, a także że jakiś przełącznik nie jest podłączony do żadnej śluzy.

Przykład zawierający trzy kanały i dwa przełączniki.

• śluza jest otwarta, jeżeli przełącznik jest włączony, a zamknięta, jeżeli przełącznik jest wyłączony,
• śluza jest zamknięta, jeżeli przełącznik jest włączony, a otwarta, jeżeli przełącznik jest wyłączony.

Bajtazar poeksperymentował trochę z przełącznikami i doszedł do wniosku, że doświadczenie programistyczne może mu się przydać do wykonania zadania. Napisz program, który na podstawie konfiguracji śluz i przełączników sprawdzi, czy da się zamknąć wszystkie kanały, i jeżeli tak, to wyznaczy stan każdego przełącznika w jednej z takich konfiguracji.

Wejście

Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite oraz , oznaczające odpowiednio liczbę kanałów i liczbę przełączników. Przełączniki są ponumerowane od do . Dodatkowo, w testach wartych co najmniej punktów, nie będzie przekraczało , a nie będzie większe niż .

Kolejne wierszy zawiera opisy kanałów; każdy kanał jest opisany w osobnym wierszu za pomocą czterech liczb całkowitych: , , , . Liczby i reprezentują przełączniki (), które sterują śluzami danego kanału. Liczby i mogą przyjmować wartości lub ; opisują one wspomniane sposoby sterowania: oznacza, że śluza jest zamknięta wtedy i tylko wtedy, gdy -ty przełącznik jest wyłączony, natomiast oznacza, że śluza jest zamknięta wtedy i tylko wtedy, kiedy -ty przełącznik jest włączony.

Wyjście

Jeżeli da się zamknąć wszystkie kanały, to na standardowe wyjście powinno zostać wypisanych wierszy. -ty z nich powinien zawierać , jeżeli -ty przełącznik powinien być wyłączony, a , jeżeli włączony. Jeżeli istnieje więcej niż jedno poprawne rozwiązanie, Twój program powinien wypisać którekolwiek z nich.

Jeżeli nie jest możliwe zamknięcie wszystkich kanałów, to Twój program powinien wypisać jeden wiersz, zawierający jedno słowo IMPOSSIBLE.

Przykład

Dla danych wejściowych:

3 2
1 0 2 1
1 0 2 0
1 1 2 1

poprawną odpowiedzią jest:

0
1

natomiast dla danych wejściowych:

2 1
1 0 1 0
1 1 1 1

poprawnym wynikiem jest:

IMPOSSIBLE

Pierwszy z przykładów odpowiada obrazkowi z treści zadania.

Autor zadania: Linas Petrauskas.