Недавно Фермер Джон увеличил размер своей фермы, теперь с точки зрения коров,
она бесконечная по размеру. Коровы представляют пастбище фермы как бесконечную
2D решётку квадратных ячеек, каждая из которых заполнена вкуснейшей травой.
(Думайте о каждой ячейке как о клетке на шахматной доске). Каждая из \(N\) коров
(\(1\le N\le 1000\)) ФД начинает в различной ячейке. Некоторые начинают, глядя на север,
а некоторые - на восток.
Каждый час корова или
- Останавливается, если трава в текущей ячейке уже съедена другой коровой.
- Съедает всю траву в текущей ячейке и перемещается на одну ячейку вперёд в своём
исходном направлении.
Через некоторое время каждая корова оставит за собой колею пустых ячеек.
Если две коровы попадут одновременно на одну и ту же ячейку с травой, они поедят вместе
и продолжат движение в своих направлениях в следующий час.
ФД не любит, когда корова прекращает пастись, и он хочет узнать, кто виноват в его
остановленных коровах. Если корова \(b\) остановилась в ячейке, которую съела корова \(a\),
тогда он считает, что корова \(a\) остановила корову \(b\). Более того, если корова \(a\)
остановила корову \(b\), а корова \(b\) остановила корову \(c\), он считает, что корова \(a\)
также остановила корову \(c\) (то есть отношение "остановила" транзитивно). Каждая корова
"виновата" в количестве коров, которые она остановила. Для каждой коровы вычислите
количество остановленных ею коров.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит целое число \(N\). Каждая из последующих \(N\) строк описывает
стартовую позицию коровы в терминах:
символ (N или E, смотри на север или на восток) и
и два неотрицательных целых числа \(x\) and \(y\) (\(0\le x\le 10^9\), \(0\le y\le 10^9\))
- координаты ячейки. Все \(x\)-координаты различны. Все \(y\)-координаты различны.
Чтобы было понятнее относительно направлений и координат, если корова
в ячейке \((x,y)\) и двигается на север, то она попадёт в ячейку \((x,y+1)\),
а если на восток - то в ячейку \((x+1, y)\).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(N\) строк. Строка \(i\) должна описывать количество коров, которые остановила
\(i\)-ая по вводу корова.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
E 3 5
N 5 3
E 4 6
E 10 4
N 11 1
E 9 2
|
0
0
1
2
1
0
|