eolymp
Змагання

USACO 2020 December

Застрять в колее (Бронза)

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

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

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

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

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

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

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

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

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

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #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
Джерело 2020 USACO Декабрь, Бронза