Problem Description

Farmer John has recently expanded his farm. From the cows’ point of view, the farm is basically infinite! The cows imagine the grazing area on the farm as an infinite two-dimensional grid made of square cells, and each cell contains delicious grass (treat each cell like a square on a chessboard). Farmer John’s $N$ cows ($1 \le N \le 50$) start in different cells. Some face north, and some face east.

Every hour, each cow does one of the following:

• If the grass in her current cell has already been eaten by another cow, then she stops.
• She eats all the grass in her current cell, and moves one cell in the direction she is facing.

After some time, each cow will leave behind a trail of cells with no grass.

If two cows move into the same grassy cell in a single move, they share the grass in that cell, and in the next hour they continue moving in the directions they are facing.

Please find the amount of grass each cow eats. Some cows will never stop, and thus eat infinitely much grass.

Input Format

The first line contains $N$. The next $N$ lines each describe a cow’s starting position, containing a character N (meaning she faces north) or E (meaning she faces east), and two nonnegative integers $x$ and $y$ ($0 \le x \le 10^9$, $0 \le y \le 10^9$) giving the cell coordinates. All $x$ coordinates are distinct, and all $y$ coordinates are distinct.

To make directions and coordinates as clear as possible: if a cow is in cell $(x, y)$ and moves north, she reaches cell $(x, y+1)$. If she moves east, she reaches cell $(x+1, y)$.

Output Format

Output $N$ lines. The $i$-th line should contain the number of grass cells eaten by the $i$-th cow in the input. If a cow can eat infinitely much grass, output Infinity for that cow.

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

Hint

Testdata Properties

• In testdata $2-5$, all coordinates are at most $100$.
• Testdata $6-10$ has no additional constraints.

Translated by ChatGPT 5