Ś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.
Przełącznik może sterować śluzą na dokładnie jeden z dwóch sposobów:
-
ś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.