Ołtarze

Limit pamięci: 32 MB

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 ze standardowego wejścia opisy świątyń,
• sprawdzi, które świątynie mogą zostać zhańbione,
• wypisze ich numery na standardowe wyjścia.

Wejście

W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba naturalna , , będąca liczbą świątyń.

W każdym z kolejnych wierszy znajduje się opis jednej świątyni (w -tym z tych wierszy opis świątyni numer ). 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 standardowego wyjścia Twój program powinien zappisać 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 na standardowe wyjście należy wypisać jedno słowo BRAK.

Przykład

Dla danych wejściowych:

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

poprawną odpowiedzią jest:

1
2
5
6

Na rysunku pokazano układ świątyń opisany w przykładzie z treści zadania. Linie przerywane pokazują możliwe drogi inwazji złych duchów.

Autor zadania: Grzegorz Jakacki.