Problem Description

This problem is translated from CEOI 2024 Day 1 Task 1「Naval battle」.

Ondra, the commander of the Czech Navy, has just been promoted to Grand Marshal and is enjoying the peace of his new position, when the government suddenly informs him that the navy will be disbanded.

Ondra is determined to prove how important the Czech Navy is. Through his spies, he learns that a massive naval battle between four countries is about to take place. If he can win this battle, it will surely be strong evidence to show the government the navy’s value.

However, the Czech Navy has neither warships nor ports. But Ondra thinks that if his spies can seize a few of the ships taking part in the battle, there may still be a chance. The key question is: how can he 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. Each warship belongs to exactly one of the four fleets: North, South, East, or West.
• The battle proceeds in rounds. In each round:
  • Every warship simultaneously moves one cell in the direction of its fleet.
  • If two or more warships occupy the same cell, they collide, sink, and disappear from the map.
• The battle ends when no more collisions occur. Surviving warships are those that remain on the map after the battle ends.

The movement directions and coordinate changes for each fleet are:

• North fleet: $y$ decreases by $1$.
• South fleet: $y$ increases by $1$.
• East fleet: $x$ increases by $1$.
• West fleet: $x$ decreases by $1$.

Input Format

The first line contains an integer $N$, the total number of warships participating in the battle. The next $N$ lines each contain three space-separated values $x_i, y_i, d_i$. Here, $x_i$ and $y_i$ give the initial position of the $i$-th warship, and the character $d_i$ indicates the direction of the fleet it belongs to; it is one of N, S, E, or W.

Initially, no two warships share the same coordinates. In other words, for any two different warships $i$ and $j$, it is impossible that both their $x$-coordinates are equal and their $y$-coordinates are also equal.

Output Format

For each surviving warship, output one line containing its index $i\ (1 \leq i \leq N)$. You may output the indices of surviving warships in any order.

If no warships survive, the output should be empty.

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

7

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

2
5

Hint

Sample Explanation 1

The initial placement of warships is shown in the figure below:

Battle process:

• In round $2$, warships $3$ and $4$ collide at $(4, 4)$.
• In round $6$, warships $1$ and $5$ collide at $(6, 6)$, and warships $2$ and $6$ collide at $(6, 8)$.

In the end, only warship $7$ survives.

Sample Explanation 2

The initial placement of warships is shown in the figure below:

In round $2$, warships $1$, $3$, and $4$ collide at $(2, 4)$, and warships $2$ and $5$ survive.

Constraints and Notes

For all input data, it holds that:

• $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 both even.

The detailed additional constraints and scores for subtasks are given in the table below.

Translated by ChatGPT 5