Description

Farmer John has recently expanded his farm, and from the cows’ point of view, the farm is basically infinitely large. The cows imagine the grazing area as an infinite two-dimensional grid made of square cells, where every cell contains tasty grass (treat each cell like a square on a chessboard). Farmer John has $N$ cows ($1 \le N \le 1000$), each initially in a different cell. Some face north, and some face east.

Every hour, each cow does one of the following:

• If the grass in the cell she is currently in has already been eaten by another cow, then she stops (and stays stopped from that moment on).
• Otherwise, she eats all the grass in her current cell, then moves one cell in the direction she is facing.

After some time, each cow will leave behind a trail of cells where the grass has been eaten.

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

Farmer John is unhappy when he sees cows that stop eating grass, so he wants to know who should be blamed for causing cows to stop. If cow $b$ stops on a cell whose grass was previously eaten by cow $a$, then we say cow $a$ blocks cow $b$. Furthermore, if cow $a$ blocks cow $b$ and cow $b$ blocks cow $c$, then we also consider cow $a$ to block cow $c$ (that is, the “blocks” relation is transitive). The amount of blame a cow receives equals the number of cows she blocks. Compute, for each cow, how many cows she is to blame for, i.e., how many cows she blocks.

Input Format

The first line contains $N$. The next $N$ lines each describe a cow’s starting position, containing a character N (meaning facing north) or E (meaning facing east), and two non-negative 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 at cell $(x, y)$ and moves north, she will arrive at cell $(x, y+1)$. If she moves east, she will arrive at cell $(x+1, y)$.

Output Format

Output $N$ lines. The $i$-th line should contain the number of cows that the $i$-th cow in the input is to blame for.

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

Hint

In the sample, cow 3 blocks cow 2, cow 4 blocks cow 5, and cow 5 blocks cow 6. By transitivity, cow 4 also blocks cow 6.

• In testdata 2–5, all coordinates are at most $2000$.
• In testdata 6–10, there are no additional restrictions.

Problem by: Brian Dean.

Translated by ChatGPT 5