Farmer John a récemment agrandi sa ferme, qui paraît désormais pratiquement infinie à ses vaches ! Elles voient le pâturage comme une grille bidimensionnelle infinie de cases carrées pleines d'herbe délicieuse (comme un échiquier infini). Chacune des $N$ vaches ($1\le N\le 50$) part d'une case différente, certaines vers le nord et d'autres vers l'est.

Chaque heure, chaque vache fait l'une des deux choses suivantes :

• Elle s'arrête si l'herbe de sa case a déjà été mangée par une autre vache.
• Elle mange toute l'herbe de sa case et avance d'une case dans la direction qu'elle regarde.

Avec le temps, chacune laisse donc derrière elle une « ornière » stérile de cases vides.

Si deux vaches arrivent dans la même case herbeuse lors du même déplacement, elles la partagent et continuent dans leurs directions respectives l'heure suivante.

Déterminez la quantité d'herbe mangée par chaque vache. Certaines ne s'arrêtent jamais et mangent donc une quantité infinie.

Entrée

La première ligne contient $N$. Chacune des $N$ lignes suivantes décrit le départ d'une vache par le caractère N (nord) ou E (est) et deux entiers non négatifs $x$ et $y$ ($0\le x\le 10^9$, $0\le y\le 10^9$), coordonnées d'une case. Les coordonnées $x$ sont toutes distinctes, de même que les coordonnées $y$.

Pour préciser les directions : depuis $(x,y)$, aller au nord mène à $(x,y+1)$, et aller à l'est à $(x+1, y)$.

Sortie

Affichez $N$ lignes. La ligne $i$ indique le nombre de cases d'herbe mangées par la vache $i$ de l'entrée. Si elle en mange une quantité infinie, affichez Infinity.

Exemples

Entrée 1

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

Sortie 1

5
3
Infinity
Infinity
2
5

Sous-tâches

• Dans les tests $2$ à $5$, toutes les coordonnées sont au plus $100$.
• Les tests $6$ à $10$ n'ont pas de contraintes supplémentaires.

Auteur du problème : Brian Dean