Problem description

Jasio po wielu latach uczenia się informatyki stwierdził, że to nie dla niego, po czym wstąpił do armii i został saperem. Przed chwilą został zrzucony z helikoptera na teren wroga, w celu rozbrojenia zakopanych tutaj min. Zaraz, zaraz, coś tu nie gra. O zgrozo, Jasio zostawił w bazie swój wykrywacz metalu! Spokojnie, to jeszcze nie czas na panikę. Wprawdzie teren jest zaminowany, ale nie w całości. W plecaku Jasia znajduje się mapa, na której zaznaczone są zaminowane obszary. Przemieszczanie się poza tymi obszarami jest całkowicie bezpieczne i Jasio planuje w ten sposób wrócić do bazy. Pytanie, czy taka bezpieczna trasa w ogóle istnieje.

Mapa dzieli teren na X ⋅ Y sektorów w kształcie jednostkowych kwadratów, ułożonych w X kolumn i Y wierszy. Kolumny ponumerowane są liczbami od 1 do X, od zachodu do wschodu, a wiersze liczbami od 1 do Y, od północy do południa. Sektor położony w i-tej kolumnie oraz j-tym wierszu oznaczamy przez (i,j).

Jasio znajduje się początkowo w sektorze (1,1), a baza w sektorze (X,Y). Każdy zaminowany obszar jest prostokątem złożonym z zaminowanych sektorów. Możesz założyć, że sektory (1,1) i (X,Y) są bezpieczne, czyli nie znajdują się w żadnym takim prostokącie. Z sektora (i,j) Jasio może przedostać się do sektorów (i+1,j), (i−1,j), (i,j+1), (i,j−1), oczywiście pod warunkiem, że są bezpieczne. Teren leżący poza mapą nie jest bezpieczny. Poniżej znajduje się rysunek, przedstawiający mapę z pierwszego testu przykładowego.

Napisz program, który ustali, czy Jasio ma szansę dostać się do bazy. W tym celu wczyta wymiary mapy i zaminowane obszary, sprawdzi czy istnieje bezpieczna trasa między pozycją Jasia a bazą i wypisze odpowiedź na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby naturalne X, Y, N, porozdzielane pojedynczymi znakami odstępu, oznaczające kolejno liczbę kolumn, wierszy i zaminowanych obszarów. W następnych N wierszach opisane są zaminowane obszary. Każdy z nich składa się z czterech liczb naturalnych x_i, y_i, x_i′, y_i′, porozdzielanych pojedynczymi znakami odstępu. Wszystkie sektory (i,j) dla x_i ≤ i ≤ x_i′ i y_i ≤ j ≤ y_i′ są zaminowane.

Wyjście

Na standardowe wyjście należy wypisać słowo TAK, jeżeli istnieje bezpieczna trasa między pozycją Jasia a bazą. W przeciwnym wypadku należy wypisać słowo NIE.

Ograniczenia

2 ≤ X, Y ≤ 10⁹, 1 ≤ N ≤ 2 000.

Przykład

12 7 5
1 2 3 3
8 2 10 6
5 1 6 4
12 1 12 6
2 6 10 7

TAK

3 3 1
1 2 3 2

NIE