Problem description

Marcin niedawno zapoznał się z problemem ustawiania hetmanów na szachownicy, którego treść jest następująca: mając daną szachownię o wymiarach N × N należy ustawić na niej N hetmanów tak, żeby żaden hetman nie atakował żadnego innego. Dla przypomnienia, hetman atakuje wszystkie figury, które stoją w tym samym rzędzie, kolumnie lub przekątnej co dany hetman.

W ramach rozgrzewki Marcin postanowił poukładać sobie hetmany na różne sposoby na szachownicy. Niestety, hetmanów jest tak dużo, że zaczął gubić się w sprawdzaniu czy na pewno żaden hetman nie atakuje żadnego innego. Marcin poprosił Cię o napisanie programu, który będzie to sprawdzał.

Wejście

W pierwszym wierszu strandardoweg wejścia znajdują się dwie liczby naturalne oddzielone pojedynczym odstępem N i M oznaczające odpowiednio wymiar szachownicy oraz liczbę postawionych hetmanów. W następnych M wierszach następują opisy położenia hetmanów. Każdy wiersz składa się z dwóch liczb całkowitych X, Y oznaczających, że w X-tym rzędzi oraz Y-tej kolumnie szachownicy stoi hetman.

Wyjście

W jednym wierszu standardowego wyjścia powinno znajdować się słowo DOBRZE, jeżeli żaden hetman nie atakuje innego hetmana oraz słowo ATAK w przeciwynym przypadku.

Ograniczenia

1 ≤ X, Y ≤ N ≤ 1 000 000, 1 ≤ M ≤ 1 000 000. Można założyć, że żadni dwaj hatmanowie nie stoją na jednym polu.

Przykład

4 3
1 1
4 2
3 4

DOBRZE

2 2
1 1
2 2

ATAK