Farmer John niedawno powiększył farmę, która dla krów jest teraz praktycznie nieskończona! Widzą pastwisko jako nieskończoną dwuwymiarową siatkę kwadratowych komórek z pyszną trawą (jak nieskończona szachownica). Każda z $N$ krów ($1\le N\le 50$) zaczyna w innej komórce, niektóre zwrócone na północ, inne na wschód.

Co godzinę każda krowa wykonuje jedno z poniższych:

• Zatrzymuje się, jeśli trawę w jej obecnej komórce zjadła już inna krowa.
• Zjada całą trawę w komórce i idzie o jedną komórkę w kierunku, w którym patrzy.

Z czasem zostawia więc za sobą jałową „koleinę” pustych komórek.

Jeśli dwie krowy w tym samym ruchu wejdą do tej samej komórki z trawą, dzielą ją i w następnej godzinie kontynuują w swoich kierunkach.

Ustal ilość trawy zjedzonej przez każdą krowę. Niektóre nigdy się nie zatrzymują i zjadają nieskończenie dużo.

Wejście

Pierwszy wiersz zawiera $N$. Każdy z kolejnych $N$ wierszy opisuje początek krowy znakiem N (północ) lub E (wschód) i dwiema nieujemnymi liczbami całkowitymi $x$ i $y$ ($0\le x\le 10^9$, $0\le y\le 10^9$), współrzędnymi komórki. Wszystkie współrzędne $x$ są różne, tak samo wszystkie $y$.

Dla jasności, z $(x,y)$ ruch na północ prowadzi do $(x,y+1)$, a na wschód do $(x+1, y)$.

Wyjście

Wypisz $N$ wierszy. Wiersz $i$ podaje liczbę komórek trawy zjedzonych przez krowę $i$ z wejścia. Przy nieskończonej ilości wypisz Infinity.

Przykład

Wejście 1

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

Wyjście 1

5
3
Infinity
Infinity
2
5

Podzadania

• W testach od $2$ do $5$ wszystkie współrzędne są najwyżej $100$.
• W testach od $6$ do $10$ nie ma dodatkowych ograniczeń.

Autor zadania: Brian Dean