Lustrzana skrzynka
Limit pamięci: 32 MB
Profesor Andrus uwielbia rozwiązywać przeróżne łamigłówki.
Jedną z jego ulubionych jest "Lustrzana Skrzynka".
Konstrukcję skrzynki najłatwiej opisać patrząc na nią z góry.
Załóżmy więc, że widzimy poziomy przekrój skrzynki narysowany w prostokątnym układzie współrzędnych.
Jest to prostokąt o bokach równoległych do osi układu,
podzielony na kwadratowych pól (ułożonych w wierszy i kolumn).
W każdym polu może być umieszczone lustro.
Lustro jest ustawione pionowo po przekątnej pola biegnącej od lewego-dolnego do prawego-górnego narożnika (przekroju) pola.
Obie strony lustra odbijają światło.
W zewnętrznych ścianach skrzynki, pośrodku każdego wiersza i każdej kolumny, znajdują się otwory, przez które może wpadać do wnętrza lub wychodzić na zewnątrz skrzynki wiązka światła.
Przez każdy otwór można wpuścić do wnętrza skrzynki wiązkę światła jedynie w kierunku prostopadłym do ściany, w której znajduje się otwór.
Taka wiązka odbijając się od lustra zmienia kierunek o 90 stopni.
Gdy wiązka przechodzi przez puste pole (takie, na którym nie ma lustra), wówczas jej kierunek nie ulega zmianie.
Otwory w ścianach skrzynki są ponumerowane od do .
Numery są nadawane otworom zgodnie z kolejnością ich występowania na obwodzie skrzynki, począwszy od otworu w lewej ścianie górnego-lewego pola (na przekroju) i następnie w kierunku przeciwnym do ruchu wskazówek zegara (czyli idąc najpierw w dół lewej ściany).
Ponieważ z zewnątrz nie widać układu luster, więc jedynym sposobem, by wywnioskować, jaki jest ten układ, jest wpuszczanie wiązek światła przez wybrane otwory i obserwowanie, przez które otwory takie wiązki wychodzą.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia rozmiar skrzynki i numery otworów, przez które wpadają i wychodzą wiązki światła,
- obliczy, na których polach znajdują się lustra, a które pola są puste,
- zapisze wynik na standardowym wyjściu.
Jeżeli istnieje więcej niż jedno rozwiązanie, to program powinien podać dowolne z nich.
Wejście
W pierwszym wierszu znajdują się dwie liczby naturalne:
(liczba wierszy pól, ) oraz
(liczba kolumn pól, ), oddzielone pojedynczym odstępem.
Każdy z kolejnych wierszy zawiera po jednej liczbie naturalnej.
Liczba w -szym wierszu oznacza numer otworu, przez który
wyjdzie wiązka światła, która wpada do skrzynki przez otwór o numerze .
Wyjście
Twój program powinien zapisać na standardowym wyjściu wierszy,
z których każdy powinien zawierać liczb oddzielonych pojedynczymi odstępami.
Liczba -ta w -ym wierszu powinna być równa
1, jeżeli na polu w -tym wierszu i -tej kolumnie
znajduje się lustro; w przeciwnym razie (gdy pole to jest puste) liczba ta powinna być równa 0.
Przykład
Dla danych wejściowych:
2 3
9
7
10
8
6
5
2
4
1
3
poprawną odpowiedzią jest:
0 1 0
0 1 1