Stuck in a Rut

Farmer John has expanded his farm so much that, from the cows' point of view, the pasture is an infinite 2D grid. Each cell of this infinite grid (think of it as chessboard squares) initially contains delicious grass. There are \(N\) cows (\(1\le N\le 50\)) starting on distinct squares. Each cow is facing either North or East.

Every hour, each cow does one of the following:

• If the cell it is currently on has already had its grass eaten by another cow, it stops moving forever.
• Otherwise, the cow eats all the grass on its current cell and moves one cell in the direction it is facing.

As time passes, each cow leaves behind a barren trail. If two cows simultaneously move onto the same grassy cell, they share the grass in that cell and continue moving in the next hour.

Your task is to determine the total number of cells each cow will have eaten. If a cow moves indefinitely (i.e. never stops), output Infinity for that cow.

For example, consider a cow that never encounters a cell where the grass was previously eaten—it will eat an infinite amount of grass. Otherwise, if a cow stops after moving \(d\) steps, then it will have eaten \(d+1\) cells (including its starting cell).

inputFormat

The first line contains an integer \(N\) (\(1\le N\le 50\)), the number of cows.

Each of the next \(N\) lines contains a character and two integers: the direction the cow is facing (N for north or E for east), followed by its starting \(x\) and \(y\) coordinates. All cows start on distinct positions.

outputFormat

Output \(N\) lines. The \(i\)-th line should contain the number of grass cells eaten by the \(i\)-th cow (in the input order). If the cow never stops, output Infinity instead.

sample

3
E 3 5
N 5 3
E 4 6

Infinity
Infinity
2