Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Un número de carretillas de tiendas llenas con explosivos están sobre un sistema de coordenadas moviéndose en una de las cuatro direcciones principales ( up, down, left, right ). Todas las carretillas se están moviendo a una velocidad de una unidad por segundo . El movimiento es continuo, por ejemplo: en un tercio de segundo una carretilla viaja un tercio de una  unidad.  Cuando dos o más carretillas colisionan (están en el mismo lugar en el mismo tiempo), hay una explosión y  todas las carretillas que toman parte en la explosión dejan de existir. Escriba un programa que, dadas los puntos iniciales y las direcciones del movimiento de todas las carretillas, determine cuáles carretillas nunca estallan.

Input

La primera línea de la entrada contiene un entero N (2 ≤ N ≤ 500), el número de carretillas. Cada una de las siguientes N líneas contienen dos enteros y una cadena. Cada par de enteros describe las coordenadas de inicio de una carretilla (entre 0 y 100 000 000, inclusive), y la cadena describe la dirección en la  cual las carretillas se mueven. Dos carretillas no comienzan en la misma coordenada.

Output

Se escribirán los índices de todas las carretillas las cuales nunca explotan, ordenados ascendentemente, un índice por línea. La primera carretilla de la entrada está identificada por 1, la segunda por 2, etc. Si no hay  carretillas que sobrevivan, escribir "none".

Sample test(s)