KOLICA - Kolica

no tags 

A number of shopping carts filled with explosives are floating in a coordinate system, in one of the four main directions (up, down, left or right). All carts are moving at a speed of one unit per second.

Movement is continuous; for example, in one third of a second, a cart travels one third of a unit.

When two or more carts collide (are at the same place at the same time), there is an explosion and all carts taking part in the collision explode and cease to exist.

Write a program that, given the starting points and directions of all carts, determines which carts never explode.

Input

The first line of input contains an integer N (2 ≤ N ≤ 500), the number of carts.

Each of the following N lines contains two integers and a string. Each pair of integers describes the starting coordinates of one cart (between 0 and 100 000 000, inclusive), and the string describes the direcction in which the cart is moving ("gore" for up, "dolje" for down, "lijevo" for left, or "desno" for right).

No two carts will start at the same coordinates.

Output

Output the indices of all carts which never explode, sorted in ascending order, one index per line. The first cart in the input is labeled 1, the second is labeled 2 etc. If no carts survive, output "nema".

Example

Input:
4
5 5 dolje
5 6 lijevo
5 7 desno
5 8 gore Output: 1
2
3
4


Input:

5
3 3 dolje
1 1 desno
5 1 lijevo
100000 500000 desno
900000 500000 lijevo

Output:
nema


Input:
3
10 0 gore
0 10 desno
15 5 lijevo
Output:
2

hide comments
[shifted to another user]: 2011-06-09 06:44:33

Could you give a hint where my code goes wrong in the failing case? Submission ID: 5216437

Last edit: 2011-06-09 06:45:00

Added by:Stjepan Glavina
Date:2011-02-28
Time limit:0.195s-0.390s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Croatian Nationals 2007