Farmer John ampliou recentemente sua fazenda, que agora parece praticamente infinita às vacas! Elas veem o pasto como uma grade bidimensional infinita de células quadradas com grama deliciosa (como um tabuleiro de xadrez infinito). Cada uma das $N$ vacas ($1\le N\le 50$) começa em uma célula diferente; algumas voltadas para o norte, outras para o leste.

A cada hora, cada vaca faz uma destas ações:

• Para se a grama de sua célula atual já foi comida por outra vaca.
• Come toda a grama da célula e avança uma célula na direção em que está voltada.

Com o tempo, cada vaca deixa atrás de si um «sulco» árido de células vazias.

Se duas vacas chegam à mesma célula com grama no mesmo movimento, compartilham a célula e continuam em suas respectivas direções na hora seguinte.

Determine a quantidade de grama comida por cada vaca. Algumas nunca param e comem uma quantidade infinita.

Entrada

A primeira linha contém $N$. Cada uma das próximas $N$ linhas descreve o início de uma vaca pelo caractere N (norte) ou E (leste) e dois inteiros não negativos $x$ e $y$ ($0\le x\le 10^9$, $0\le y\le 10^9$), as coordenadas da célula. Todas as coordenadas $x$ são distintas, assim como as coordenadas $y$.

Para esclarecer as direções, de $(x,y)$ ir ao norte leva a $(x,y+1)$, enquanto ir ao leste leva a $(x+1, y)$.

Saída

Imprima $N$ linhas. A linha $i$ indica quantas células de grama a vaca $i$ da entrada come. Se a quantidade for infinita, imprima Infinity.

Exemplos

Entrada 1

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

Saída 1

5
3
Infinity
Infinity
2
5

Subtarefas

• Nos casos $2$ a $5$, todas as coordenadas são no máximo $100$.
• Nos casos $6$ a $10$, não há restrições adicionais.

Autor do problema: Brian Dean