P5938 [POI 1999 R3] Altar Problem

In Chinese folklore, people believe that ghosts can move only along straight lines. When building temples, this is very important.

Each temple is built on a rectangular area whose sides are parallel to the north-south and east-west directions. No two rectangles may have a common point. The entrance is located at the middle of one of the four walls, and the door width is equal to half of the wall length. The altar is located at the center of the temple, where the diagonals of the rectangle intersect. If a ghost appears at this point, then the temple is desecrated if and only if there exists a ray starting from the altar, passing through the entrance to the outside, and not intersecting or touching the walls of any other temple (located in areas parallel to the building area). In other words, it must be possible to draw a straight line from the altar to infinity within the building area without hitting any wall.

The first line contains an integer $n$. The next $n$ lines describe the temples. Line $i + 1$ contains the description of the $i$-th temple: four non-negative integers not greater than $8000$ (the first two numbers are the coordinates of the northwest corner of the temple, and the next two are the coordinates of the opposite southeast corner) and one letter `E`, `W`, `S`, or `N` indicating the direction of the wall where the entrance is located (`E` - east, `W` - west, `S` - south, `N` - north). They are separated by single spaces.

In the next lines, your program should output, in increasing order, the indices of the temples that can be desecrated by a ghost. Output one index per line. If there is no such index, output `BRAK`.

### Sample Explanation  ### Constraints For $100\%$ of the testdata, $1 \le n \le 1000$. Translated by ChatGPT 5