Farmer John недавно расширил ферму, и для коров она теперь практически бесконечна! Пастбище для них — бесконечная двумерная сетка квадратных клеток с вкусной травой (как бесконечная шахматная доска). Каждая из $N$ коров ($1\le N\le 50$) начинает в отдельной клетке; некоторые смотрят на север, другие на восток.

Каждый час каждая корова либо

• Останавливается, если траву в текущей клетке уже съела другая корова.
• Съедает всю траву в текущей клетке и идёт на одну клетку в направлении, куда смотрит.

Со временем за каждой коровой остаётся бесплодная «колея» из пустых клеток.

Если две коровы одним и тем же движением попадают в одну клетку с травой, они делят её и в следующий час продолжают движение каждая в своём направлении.

Определите, сколько травы съест каждая корова. Некоторые никогда не останавливаются и съедают бесконечно много травы.

Входные данные

Первая строка содержит $N$. Каждая из следующих $N$ строк описывает исходную позицию коровы символом N (север) или E (восток) и двумя неотрицательными целыми координатами $x$ и $y$ ($0\le x\le 10^9$, $0\le y\le 10^9$). Все координаты $x$ различны, и все координаты $y$ тоже различны.

Для ясности: из клетки $(x,y)$ движение на север приводит в $(x,y+1)$, а на восток — в $(x+1, y)$.

Выходные данные

Выведите $N$ строк. Строка $i$ должна сообщать количество клеток травы, съеденных коровой $i$ во входных данных. Для бесконечного количества выведите Infinity.

Примеры

Входные данные 1

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

Выходные данные 1

5
3
Infinity
Infinity
2
5

Подзадачи

• В тестах с $2$ по $5$ все координаты не превосходят $100$.
• В тестах с $6$ по $10$ нет дополнительных ограничений.

Автор задачи: Brian Dean