Застрять в колее (Бронза)
Застрять в колее (Бронза)
Фермер Джон недавно увеличил размер своей фермы, так что с точки зрения его коров она стала бесконечно большой! Коровы думают о пастбищах на ферме как о бесконечной двумерной сетке квадратных "ячеек", каждая из которых заполнена восхитительной травой (каждую ячейку представляйте как квадрат на бесконечной шахматной доске). Каждая из 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".
6 E 3 5 N 5 3 E 4 6 E 10 4 N 11 2 N 8 1
5 3 Infinity Infinity 2 5