Rekurencyjna mrówka

Limit pamięci: 32 MB

Mrówka ma obejść wszystkie pola szachownicy poza polami zabronionymi — każde pole dokładnie jeden raz. Obchodzenie musi się zacząć w polu startowym leżącym w lewym górnym rogu i zakończyć na polu leżącym na brzegu szachownicy (mrówka na końcu opuszcza szachownicę). Zakładamy, że pole startowe nie jest zabronione. W jednym kroku mrówka może przejść do jednego z co najwyżej czterech sąsiednich pól szachownicy (w górę, dół, lewo lub prawo).

Mrówka obchodzi szachownicę w sposób w pewnym sensie rekurencyjny: aby obejść kwadrat dzieli go na cztery części (rekurencyjne ćwiartki) o rozmiarach , a następnie obchodzi każdą z nich, to znaczy, jeżeli mrówka wejdzie do jednej z ćwiartek, to może z niej wyjść dopiero wtedy, gdy obejdzie wszystkie nie zabronione pola w tej ćwiartce.

Rysunek przedstawia dwie trasy rekurencyjnej wędrówki mrówki na szachownicy o rozmiarach , od pola startowego do pola leżącego odpowiednio na górnym oraz lewym brzegu szachownicy.

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia liczbę całkowitą dodatnią określającą jednoznacznie rozmiar szachownicy oraz liczbę pól zabronionych i ich listę,
• na każdym z czterech brzegów szachownicy znajduje pole, na którym może się zakończyć rekurencyjna wędrówka mrówki, spełniająca podane wyżej warunki lub stwierdza, że takiego pola nie ma,
• zapisuje wyniki na standardowe wyjście.

Uwaga: każde z czterech pól narożnych należy do dwóch brzegów szachownicy.

Wejście

W pierwszym wierszu standardowego wejścia jest zapisana liczba całkowita dodatnia , . W drugim wierszu jest zapisana liczba pól zabronionych , .

W każdym z kolejnych wierszy jest zapisana para liczb całkowitych nieujemnych oddzielonych pojedynczym odstępem, są to dwie współrzędne: numer wiersza oraz numer kolumny odpowiedniego zabronionego pola. Wiersze szachownicy numerujemy od góry w dół, a kolumny od lewej do prawej, od do .

Wyjście

W każdym z czterech kolejnych wierszy standardowego wyjścia należy zapisać dwie liczby całkowite nieujemne oddzielone pojedynczym odstępem — współrzędne (numer wiersza i numer kolumny) odpowiedniego końcowego pola rekurencyjnej trasy mrówki leżącego na: górnym, prawym, dolnym oraz lewym brzegu szachownicy (w takiej kolejności) lub jedno słowo NIE, jeśli takiego pola nie ma.

Przykład

Dla danych wejściowych:

3
17
2 0
1 0
3 0
6 0
7 0
6 1
7 1
6 2
7 2
6 3
7 3
0 2
0 3
0 6
0 7
1 6
1 7

poprawną odpowiedzią jest:

0 4
NIE
NIE
4 0

Autor zadania: Wojciech Rytter.