Mrówka ma obejść wszystkie pola szachownicy 2ⁿ x 2ⁿ 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 2^k x 2^k dzieli go na cztery części (rekurencyjne ćwiartki) o rozmiarach 2^k-1 x 2^k-1, 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 1 przedstawia dwie trasy rekurencyjnej wędrówki mrówki na szachownicy o rozmiarach 2³ x 2³, od pola startowego (0,0) do pola leżącego odpowiednio na górnym oraz lewym brzegu szachownicy.

Rysunek 1

Zadanie

• wczytuje z pliku tekstowego REK.IN liczbę całkowitą dodatnią n określającą jednoznacznie rozmiar szachownicy 2ⁿ x 2ⁿ oraz liczbę m 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 w pliku tekstowym REK.OUT.

Wejście

W drugim wierszu jest zapisana liczba pól zabronionych m <= 50.

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

Wyjście

Przykład

3
15
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

0 4
NIE
NIE
4 0

Twój program powinien szukać pliku REK.IN w katalogu bieżącym i tworzyć plik REK.OUT również w bieżącym katalogu. Plik zawierający napisany przez Ciebie program w postaci źródłowej powinien mieć nazwę REK.???, gdzie zamiast ??? należy wpisać co najwyżej trzyliterowy skrót nazwy użytego języka programowania. Ten sam program w postaci wykonalnej powinien być zapisany w pliku REK.EXE.