FRAKTAL - konkurs programistyczny

Neo znajduje się w biurze. Przedstawmy je w postaci planszy:

• Plansza ma 4n + 1 wierszy i tyle samo kolumn.
• Wiersze ponumerowane są od 0, od góry do dołu.
• Kolumny ponumerowane są od 0, od lewej do prawej.
• Pola, których numer wiersza lub numer kolumny jest podzielny przez 4 to przejścia.
• Pozostałe pola to boksy biurowe.

Dla n = 2 plansza przedstawia się następująco:

.........
.###.###.
.###.###.
.###.###.
.........
.###.###.
.###.###.
.###.###.
.........

Gdzie kropka oznacza przejście, zaś kratka oznacza boks biurowy.

W biurze jest agent, który szuka Neo. Początkowo agent znajduje się na polu 0 4n (wiersz kolumna). Agent przemieszcza się według następujących zasad:

• Z aktualnego pola może się przenieść na dowolne inne pole będące przejściem.
• Nigdy nie przeniesie się na pole 0 0.
• Nigdy nie przeniesie się na pole 4n 4n.
• Nigdy nie przeniesie się na pole, na którym aktualnie znajduje się Neo.

Nasz bohater początkowo znajduje się na polu 0 0 i musi się dostać na pole 4n 4n. Neo przemieszcza się według następujących zasad:

• Z aktualnego pola może przejść tylko na pole mające z nim wspólny bok, które jest przejściem.
• Nigdy nie przejdzie na pole, na którym aktualnie znajduje się agent.

Nasz bohater zadzwoni do Ciebie. Neo poda Ci wartość n. Następnie będzie Ci przekazywał komunikaty. Każdy komunikat może być jednego z dwóch typów:

• 1 w k - Neo przeszedł, zgodnie z zasadami, na pole w wierszu w i kolumnie k.
• 2 w k - Agent przeniósł się, zgodnie z zasadami, na pole w wierszu w i kolumnie k.

Dla każdego komunikatu typu 1 podaj kierunek, w którym Neo ma przejść, aby znaleźć się w minimalnej odległości od pola 4n 4n. Pamiętaj, że rozpatrujesz aktualną sytuację na planszy.

Ponieważ Neo jest bardzo zestresowany, niekoniecznie musi się przemieszczać zgodnie z Twoimi wskazówskami.

Wejście

W pierwszej linii znajduje się liczba całkowita n ∈ [1, 10].

W kolejnych liniach znajdują się komunikaty. Liczba komunikatów jest nieokreślona, ale nie będzie większa niż 1497247.

Każdy komunikat ma jedną z dwóch postaci:

• 1 w k
• 2 w k

Gdzie w oznacza numer wiersza, zaś k oznacza numer kolumny. Numer wiersza oraz numer kolumny zawierają się w przedziale [0, 4n].

Po dojściu do celu, czyli wczytaniu komunikatu 1 4n 4n, powinieneś zakończyć program.

Wyjście

Dla każdego komunikatu typu 1 podaj kierunek, w którym Neo ma przejść, aby znaleźć się w minimalnej odległości od pola 4n 4n. Pamiętaj, że rozpatrujesz aktualną sytuację na planszy. Możliwe kierunki to:

• NAPRZOD
• LEWO
• PRAWO
• ZAWROC

Przykład

Wejście:

2
1 0 1
2 0 4
1 0 2
1 0 3
1 0 2
1 0 1
1 0 0
1 1 0
1 2 0
1 3 0
1 4 0
1 4 1
1 4 2
1 4 3
2 4 5
1 4 4
1 5 4
1 6 4
1 7 4
2 8 3
1 8 4
1 8 5
1 8 6
1 8 7
1 8 8

Wyjście:

NAPRZOD
ZAWROC
ZAWROC
NAPRZOD
NAPRZOD
LEWO
NAPRZOD
NAPRZOD
NAPRZOD
LEWO
NAPRZOD
NAPRZOD
NAPRZOD
PRAWO
NAPRZOD
NAPRZOD
NAPRZOD
LEWO
NAPRZOD
NAPRZOD
NAPRZOD