Farmer John amplió recientemente su granja, ¡que ahora parece prácticamente infinita a sus vacas! Ven el pasto como una cuadrícula bidimensional infinita de celdas cuadradas llenas de hierba deliciosa (como un tablero de ajedrez infinito). Cada una de sus $N$ vacas ($1\le N\le 50$) parte de una celda distinta; unas miran al norte y otras al este.

Cada hora, cada vaca realiza una de estas acciones:

• Se detiene si otra vaca ya comió la hierba de su celda actual.
• Come toda la hierba de su celda y avanza una celda en la dirección que mira.

Con el tiempo, cada vaca deja detrás un «surco» estéril de celdas vacías.

Si dos vacas llegan a la misma celda con hierba en el mismo movimiento, la comparten y siguen en sus respectivas direcciones la hora siguiente.

Determina cuánta hierba come cada vaca. Algunas nunca se detienen y comen una cantidad infinita.

Entrada

La primera línea contiene $N$. Cada una de las siguientes $N$ líneas describe el inicio de una vaca con el carácter N (norte) o E (este) y dos enteros no negativos $x$ e $y$ ($0\le x\le 10^9$, $0\le y\le 10^9$), las coordenadas de una celda. Todas las coordenadas $x$ son distintas, y lo mismo ocurre con las $y$.

Para aclarar las direcciones, desde $(x,y)$ ir al norte lleva a $(x,y+1)$, e ir al este lleva a $(x+1, y)$.

Salida

Imprime $N$ líneas. La línea $i$ indica cuántas celdas de hierba come la vaca $i$ de la entrada. Si come una cantidad infinita, imprime Infinity.

Ejemplos

Entrada 1

6
E 3 5
N 5 3
E 4 6
E 10 4
N 11 2
N 8 1

Salida 1

5
3
Infinity
Infinity
2
5

Subtareas

• En los casos $2$ a $5$, todas las coordenadas son como máximo $100$.
• En los casos $6$ a $10$ no hay restricciones adicionales.

Autor del problema: Brian Dean