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 direction 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