## ALTARS - The Altars

According to Chinese folk beliefs evil spirits can move only on a straight line. It is of a great importance when temples are built. The temples are constructed on rectangular planes with sides parallel to the north - south or east - west directions. No two of the rectangles have common points. An entrance is situated in the middle of one of four walls and its width is equal to the half of the length of the wall. An altar appears in the center of the temple, where diagonals of the rectangle intersect. If an evil spirit appears in this point, a temple will be profaned. It may happen only if there exists a ray which runs from an altar, through an entrance to infinity and neither intersects nor touches walls of any temple (on a plane parallel to the plane of a construction area), i.e. one can draw at a construction area a line which starts at the altar and runs to the infinity without touching any wall.

### Task

Write a program which:

- reads descriptions of the temples from the standard input,
- verifies which temples could be profaned,
- writes their numbers to the standard output.

### Input

The number of test cases t is in the first line of input, then t test cases follow separated by an empty line.
In the first line of each test case one integer *n*, the number of temples
* 1 <= n <= 1000,* is written.

In each of the following * n* lines there is a description of one temple (in *i*-th line a description
of the* i-*th
temple). The description of a temple consists of four non-negative
integers,
not greater than 8000 and a letter E, W, S or N. Two first numbers are
coordinates of a temple's northern-west corner and two following are
coordinates of an opposite southern-east corner. In order to
specify coordinates of a point first we give its geographical
longitude, which increases from the
west to the east, and then its latitude, which increases from the south
to the
north. The fifth element of the description indicates the wall with the
entrance (E - Eastern, W - Western, S - Southern, N - Northern).
The
elements of the temple's description are separated by single spaces.

### Output

In the following lines of the output for each test case your program should write in ascending order numbers of the temples, which may be profaned by an evil spirit. Each number is placed in a separate line. If there are no such numbers, you should write one word: NONE.

### Example

`Sample input`

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

`Sample output`

1 2 5 6

The picture shows the temples described in the example. The dashed lines show possible routes of evil spirits.

Added by: | Piotr Łowiec |

Date: | 2004-09-13 |

Time limit: | 1.318s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: NODEJS PERL6 VB.NET |

Resource: | 6th Polish Olympiad in Informatics, stage 3 |