Według chińskich wierzeń ludowych złe duchy mogą poruszać się tylko po linii prostej. Ma to istotne znaczenie przy budowie świątyń. Świątynie są budowane na planach prostokątów o bokach równoległych do kierunków północ-południe oraz wschód-zachód. Żadne dwa z tych prostokątów nie mają punktów wspólnych. Po środku jednej z czterech ścian jest wejście, którego szerokość jest równa połowie długości tej ściany. W centrum świątyni (na przecięciu przekątnych prostokąta) znajduje się ołtarz. Jeśli znajdzie się tam zły duch, świątynia zostanie zhańbiona. Tak może się zdarzyć, jeśli istnieje półprosta (w płaszczyźnie równoległej do powierzchni terenu), która biegnie od ołtarza w centrum świątyni przez otwór wejściowy aż do nieskończoności, nie przecinając i nie dotykając po drodze żadnej ściany, tej lub innej świątyni.

Zadanie

Napisz program, który:

• wczyta z pliku tekstowego OLT.IN opisy świątyń,
• sprawdzi, które świątynie mogą zostać zhańbione,
• zapisze ich numery w pliku tekstowym OLT.OUT.

Wejście

W pierwszym wierszu pliku wejściowego OLT.IN jest zapisana jedna liczba naturalna n, 1 <= n <= 1000, będąca liczbą świątyń.

W każdym z kolejnych n wierszy znajduje się opis jednej świątyni (w i-tym z tych wierszy opis świątyni numer i). Opis świątyni składa się z czterech nieujemnych liczb całkowitych, nie większych niż 8000, oraz jednej litery E, W, S lub N. Pierwsze dwie liczby, to współrzędne północno-zachodniego narożnika świątyni, a dwie następne, to współrzędne przeciwległego, południowo-wschodniego narożnika. Określając współrzędne punktu podajemy najpierw jego długość geograficzną (która rośnie z zachodu na wschód), a następnie --- szerokość geograficzną, która rośnie z południa na północ. Piąty element opisu wskazuje ścianę, na której znajduje się wejście do świątyni (E --- wschodnią, W --- zachodnią, S --- południową, N --- północną). Kolejne elementy opisu świątyni są pooddzielane pojedynczymi odstępami.

Wyjście

W kolejnych wierszach pliku tekstowego OLT.IN Twój program powinien zapisać w porządku rosnącym numery świątyń, które mogą zostać zhańbione przez złego ducha, każdy numer w osobnym wierszu. Jeżeli takich świątyń nie ma, to w pliku OLT.OUT należy zapisać jedno słowo BRAK.

Przykład

Dla pliku wejściowego OLT.IN

6
1 7 4 1 E
3 9 11 8 S
6 7 10 4 N
8 3 10 1 N
11 4 13 1 E
14 8 20 7 W

1
2
5
6