Exploding Balls

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.

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.

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.