Teleporty

Limit pamięci: 32 MB

Wielki Czarodziej Bajtalf stworzył na Bałtyku dwie wyspy: Bornholm i Gotlandię. Na wyspach rozmieścił magiczne teleporty. Teleporty służa do szybkiego "podróżowania" - osoba umieszczona w jednym z teleportów w jednej chwili może się przenieść do innego teleportu. W każdym teleporcie, w trakcie produkcji, wpisuje się identyfikator jego teleportu docelowego, tzn. takiego, do którego może on przenosić "podróżników". Identyfikatora nie można już potem zmienić. Teleporty zostały rozmieszczone tak, by dla każdego teleportu, jego teleport docelowy znajdował się na drugiej wyspie.

Każdy teleport może być nastawiony na:

• nadawanie - wówczas osoba, która się w nim znajduje zostaje przeniesiona do teleportu docelowego, o ile jest on (teleport docelowy) ustawiony na odbiór (patrz niżej),
• odbiór - wówczas może przyjąć podróżnika z innego teleportu.

Pewnego dnia Wielki Czarodziej Bajtalf nakazał swoim uczniom, by nastawili teleporty tak, aby żaden z nich nie był bezużyteczny, tzn. tak, aby dla każdego teleportu nastawionego na odbiór istniał teleport przenoszący do niego podróżników nastawiony na nadawanie, i na odwrót, dla każdego teleportu nastwionego na nadawanie, jego docelowy teleport był nastawiony na odbiór.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opisy teleportów znajdujących się na obu wyspach,
• wyznaczy, jak należy nastawić teleporty, by żaden z nich nie był bezużyteczny,
• zapisze wynik na standardowym wyjściu.

Wejście

W pierwszym wierszu znajdują się dwie liczby całkowite i , , oddzielone pojedynczym odstępem; oznacza liczbę teleportów znajdujących się na Bornholmie, a - liczbę teleportów znajdujących się na Gotlandii. Teleporty na obu wyspach są ponumerowane odpowiednio od do i od do . Drugi wiersz pliku wejściowego zawiera dodatnich liczb całkowitych (nieprzekraczających i oddzielonych pojedynczymi odstępami); -ta z tych liczb jest numerem teleportu na Gotlandii, który jest teleportem docelowym -tego teleportu z Bornholmu. Trzeci wiersz zawiera analogiczne dane dla teleportów z Gotlandii, tzn. dodatnich liczb całkowitych (nieprzekraczających i oddzielonych pojedynczymi odstępami); -ta z tych liczb jest numerem teleportu na Bornholmie, który jest teleportem docelowym -tego teleportu z Gotlandii.

Wyjście

Twój program powinien zapisać na standardowym wyjściu dwa wiersze opisujące, jak należy nastawić teleporty, by żaden z nich nie był bezużyteczny. W pierwszym wierszu powinien znaleźć się opis ustawień teleportów na Bornholmie, a w drugim - opis ustawień teleportów na Gotlandii. Każdy opis, to napis długości równej odpowiednio i złożony z zer lub jedynek. Jeżeli -ty znak w wierszu jest równy 1, to oznacza, że teleport o numerze (na danej wyspie) jest ustawiony na nadawanie; jeśli odpowiedni znak jest równy 0 - to teleport jest nastawiony na odbiór.

Przykład

Dla danych wejściowych:

4 5
3 5 2 5
4 4 4 1 3

poprawną odpowiedzią jest:

0110
10110