Problem Description

Translated from CEOI 2024 Day1 T1「Naval battle」

Commander Ondra of the Czech Navy has just been promoted to Grand Admiral and is enjoying the stability of his new position when he is suddenly notified that the navy is to be disbanded.

Ondra is determined to prove the importance of the Czech Navy. Through his spies, he has learned of an imminent naval battle involving four major powers. Winning this battle would undoubtedly demonstrate the value of the navy to the government.

However, the Czech Navy has neither warships nor ports. But Ondra thinks that if his spies can capture a few of the participating ships, there might still be a chance. The key is to predict which ships will survive this naval battle.

The rules of the naval battle are as follows:
- Before the battle, the $i$-th warship is located at coordinates $(x_i, y_i)$, where both $x_i$ and $y_i$ are even numbers. Each warship belongs to one of the North, South, East, or West fleets.
- The battle proceeds in rounds. Each round:
- Each warship moves one grid towards the direction of its fleet.
- If two or more warships occupy the same grid, they collide and sink, disappearing from the map.
- The battle ends when no more collisions occur. Surviving warships are those that remain on the map after the battle.

The movement directions and coordinate changes for each fleet are as follows:
- North Fleet: Decrease $y$ coordinate by $1$
- South Fleet: Increase $y$ coordinate by $1$
- East Fleet: Increase $x$ coordinate by $1$
- West Fleet: Decrease $x$ coordinate by $1$

Input Format

The first line contains an integer $N$, representing the total number of warships participating in the battle. The next $N$ lines each contain three space-separated integers $x_i, y_i, d_i$. $x_i$ and $y_i$ represent the initial position of the $i$-th warship, and the character $d_i$ represents the direction of the $i$-th warship's fleet, which can be N, S, E, or W.

Initially, no two warships have the same coordinates. In other words, for any two different warships $i$ and $j$, their $x$ coordinates $x_i$ and $x_j$ cannot be equal simultaneously, nor can their $y$ coordinates $y_i$ and $y_j$.

Output Format

For each surviving warship, output a single line containing the ship's number $i\ (1 \leq i \leq N)$. You can output the numbers of the surviving ships in any order.

If there are no surviving warships, the output should be empty.

Sample Input and Output

Sample Input #1

7
0 6 E
0 8 E
2 4 E
4 2 S
6 0 S
6 2 S
6 4 S

Sample Output #1

7

Sample Input #2

5
4 0 S
0 2 E
2 2 E
4 4 N
6 6 W

Sample Output #2

2
5

Notes/Hints

Sample Explanation 1

Initial warship distribution is as follows:

Battle process:
- In the $2$nd round, warships $3$ and $4$ collide at $(4, 4)$.
- In the $6$th round, warships $1$ and $5$ collide at $(6, 6)$, and warships $2$ and $6$ collide at $(6, 8)$.

Only warship $7$ survives.

Sample Explanation 2

Initial warship distribution is as follows:

In the $2$nd round, warships $1$, $3$, and $4$ collide at $(2, 4)$, leaving warships $2$ and $5$ as survivors.

Data Range and Hints

For all input data, the following conditions are satisfied:

• $2 \leq N \leq 2 \cdot 10^5$
• $0 \leq x_i, y_i \leq 10^9\ (1 \leq i \leq N)$, and $x_i, y_i$ are even numbers

Detailed subtask additional constraints and scores are as follows:

见题面 Input 部分

见题面 Output 部分