Фермер Джон недавно увеличил размер своей фермы, так что с точки зрения его коров она стала бесконечно большой! Коровы думают о пастбищах на ферме как о бесконечной двумерной сетке квадратных "ячеек", каждая из которых заполнена восхитительной травой (каждую ячейку представляйте как квадрат на бесконечной шахматной доске). Каждая из n коров фермера Джона стартует в разных ячейках; некоторые начинают движение на север, а некоторые - на восток.

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

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

Поэтому со временем каждая корова оставляет за собой бесплодную "колею" пустых клеток.

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

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

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

Первая строка содержит число n (1 ≤ n ≤ 50). Каждая из следующих n строк описывает начальное местоположение коровы в виде символа, которым является либо N (ориентация на север), либо E (ориентация на восток) и два неотрицательных целых числа x и y (0 ≤ x ≤ 109, 0 ≤ y ≤ 109) - координаты ячейки. Все x - координаты различны, как различны и y - координаты.

Чтобы быть максимально ясным относительно направлений и координат, отметим, что если корова находится в ячейке (x, y) и движется на север, то она окажется в ячейке (x, y + 1). Если корова движется на восток, то она окажется в ячейке (x + 1, y).

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

Выведите n строк: i-ая строка должна описывать количество клеток травы, которое съест i-ая корова. Если корова съест бесконечное количество травы, то для нее выведите "Infinity".