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

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

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

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

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

Фермер Джон недоволен, когда видит переставшихся пастись коров, и хочет узнать кого обвинить в том, что его коровы остановились. Если корова b остановилась в ячейке, которую изначально съела корова a, то будем говорить что корова a остановила корову b. Более того, если корова a остановила корову b, а корова b остановила корову c, то будем говорить что корова a также остановила корову c (что то есть отношение "остановить" транзитивно). Каждую корову обвиняют в соответствии с количеством остановленных коров. Вычислите количество обвинений, возложенных на каждую корову, то есть количество коров, которых она остановила.

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

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

Если корова находится в точке (x, y) и движется на север, то она окажется в точке (x, y + 1). Если она вместо этого двинется на восток, то окажется в точке (x + 1, y).

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

Выведите n строк. Строка номер i должна содержать значение вины i-ой коровы из входных данных.

Пример

В этом примере корова 3 останавливает корову 2, корова 4 останавливает корову 5 и корова 5 останавливает корову 6. По транзитивности корова 4 также останавливает корову 6.