Exploding Balls

Time limit1sMemory limit128 MB

Summary

Given N balls moving in one of four axis directions at unit speed, find which balls never collide with another ball at the same point and time.

Level: Medium7 of 10
Topics: Simulation, Math, Sorting
Solved: No attempts yet

Problem

Several balls are placed on a coordinate plane. Each ball moves only in one of four directions: up, down, left, or right. Every ball moves at speed 1 per second. The movement is continuous, so during 1/3 second a ball moves by 1/3.

If two or more balls reach the same position at the same time, those balls explode and disappear. A ball that has already disappeared cannot participate in later collisions.

Given each ball's starting point and direction, determine the numbers of the balls that never explode.

Input

The first line contains the number of balls N. (2 <= N <= 500)

Each of the next N lines contains the starting coordinates of one ball and its moving direction. Each coordinate is an integer between 0 and 100,000,000, inclusive, and the direction is one of up, down, left, and right.

No two balls have the same starting coordinates.

Output

Print the numbers of the balls that never explode, in increasing order, one per line. The first ball in the input is numbered 1, the second ball is numbered 2, and so on.

If every ball explodes, print all.

Examples3

Example 1

Input

4
5 5 down
5 6 left
5 7 right
5 8 up

Expected output

Example 2

Input

5
3 3 down
1 1 right
5 1 left
100000 500000 right
900000 500000 left

Expected output

all

Example 3
Input
```
3
10 0 up
0 10 right
15 5 left
```
Expected output
```
2
```