Farmer John hat kürzlich seinen Hof erweitert, der für seine Kühe nun praktisch unendlich groß ist! Die Weide ist für sie ein unendliches zweidimensionales Gitter quadratischer Zellen mit köstlichem Gras (wie ein unendliches Schachbrett). Jede der $N$ Kühe ($1\le N\le 50$) startet in einer anderen Zelle, manche nach Norden, andere nach Osten blickend.

Jede Stunde tut jede Kuh eines von Folgendem:

• Sie hält an, falls das Gras ihrer aktuellen Zelle bereits von einer anderen Kuh gefressen wurde.
• Sie frisst das gesamte Gras ihrer Zelle und geht eine Zelle in Blickrichtung vorwärts.

Mit der Zeit hinterlässt jede Kuh daher eine kahle „Spur“ leerer Zellen.

Wenn zwei Kühe im selben Zug auf dieselbe grasbewachsene Zelle gelangen, teilen sie diese und gehen in der nächsten Stunde in ihren jeweiligen Richtungen weiter.

Bestimme die von jeder Kuh gefressene Grasmenge. Manche halten nie an und fressen unendlich viel.

Eingabe

Die erste Zeile enthält $N$. Jede der nächsten $N$ Zeilen beschreibt den Start einer Kuh mit dem Zeichen N (Norden) oder E (Osten) und zwei nichtnegativen ganzen Zahlen $x$ und $y$ ($0\le x\le 10^9$, $0\le y\le 10^9$), den Zellkoordinaten. Alle $x$-Koordinaten sind verschieden, ebenso alle $y$-Koordinaten.

Zur Klarstellung: Aus $(x,y)$ führt ein Schritt nach Norden zu $(x,y+1)$, nach Osten zu $(x+1, y)$.

Ausgabe

Gib $N$ Zeilen aus. Zeile $i$ enthält die Anzahl Zellen Gras, die Kuh $i$ der Eingabe frisst. Bei unendlicher Menge gib Infinity aus.

Beispiele

Eingabe 1

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

Ausgabe 1

5
3
Infinity
Infinity
2
5

Teilaufgaben

• In Testfällen $2$ bis $5$ sind alle Koordinaten höchstens $100$.
• In Testfällen $6$ bis $10$ gibt es keine zusätzlichen Einschränkungen.

Aufgabenautor: Brian Dean