Farmer John ha recentemente ampliato la fattoria, che ora alle mucche sembra praticamente infinita! Vedono il pascolo come una griglia bidimensionale infinita di celle quadrate piene di erba deliziosa (come una scacchiera infinita). Ognuna delle $N$ mucche ($1\le N\le 50$) parte da una cella diversa, alcune rivolte a nord, altre a est.

Ogni ora, ogni mucca compie una di queste azioni:

• Si ferma se l'erba della cella attuale è già stata mangiata da un'altra mucca.
• Mangia tutta l'erba della cella e avanza di una cella nella direzione in cui guarda.

Nel tempo ogni mucca lascia quindi un «solco» sterile di celle vuote dietro di sé.

Se due mucche raggiungono la stessa cella erbosa nello stesso movimento, la condividono e continuano nelle rispettive direzioni nell'ora successiva.

Determina quanta erba mangia ogni mucca. Alcune non si fermano mai e ne mangiano una quantità infinita.

Input

La prima riga contiene $N$. Ognuna delle successive $N$ righe descrive l'inizio di una mucca con il carattere N (nord) o E (est) e due interi non negativi $x$ e $y$ ($0\le x\le 10^9$, $0\le y\le 10^9$), coordinate della cella. Tutte le coordinate $x$ sono distinte, e lo stesso vale per le $y$.

Per chiarire le direzioni, da $(x,y)$ andare a nord porta a $(x,y+1)$, mentre andare a est porta a $(x+1, y)$.

Output

Stampa $N$ righe. La riga $i$ indica quante celle di erba mangia la mucca $i$ dell'input. Per una quantità infinita, stampa Infinity.

Esempi

Input 1

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

Output 1

5
3
Infinity
Infinity
2
5

Sottoproblemi

• Nei casi $2$–$5$ tutte le coordinate sono al massimo $100$.
• Nei casi $6$–$10$ non ci sono vincoli aggiuntivi.

Autore del problema: Brian Dean