P10801 [CEOI 2024] 海战

**题目译自 [CEOI 2024](https://ceoi2024.fi.muni.cz/) Day1 T1「[Naval battle](https://ceoi2024.fi.muni.cz/page/tasks/statements/battle.pdf)」** 捷克海军司令官翁德拉刚刚晋升为大元帅，正享受着新职位的安稳，却突然被政府通知海军将被裁撤。 翁德拉决心证明捷克海军的重要性。他通过间谍得知，一场四国海军巨舰对决即将展开。如果能赢得这场战役，无疑能向政府有力地展示海军价值。 然而，捷克海军既无战舰也无港口。但翁德拉想到，如果他的间谍能夺取几艘参战舰艇，或许还有一线生机。关键是，如何预知哪些船能在这场海战中幸存下来呢？ 海战规则如下： - 战前，第 $i$ 艘战舰位于坐标 $(x_i, y_i)$ 处，其中 $x_i$ 和 $y_i$ 均为偶数。每艘战舰隶属于北方、南方、东方或西方舰队之一。 - 海战分回合进行。每回合： - 每艘战舰同时向其所属舰队方向移动一格。 - 如果两艘或以上战舰占据同一格，它们将相撞沉没，从海图上消失。 - 当不再发生碰撞时，海战结束。存活的战舰是指海战结束后仍留在海图上的战舰。 各舰队战舰的移动方向及坐标变化如下： - 北方舰队：$y$ 坐标减 $1$ - 南方舰队：$y$ 坐标加 $1$ - 东方舰队：$x$ 坐标加 $1$ - 西方舰队：$x$ 坐标减 $1$

第一行输入一个整数 $N$，代表参与海战的舰船总数。 接下来是 $N$ 行，每行包含三个用空格隔开的整数 $x_i, y_i, d_i$。$x_i$ 和 $y_i$ 表示第 $i$ 艘舰船的初始位置，字符 $d_i$ 表示第 $i$ 艘舰船所属舰队的方向，它可以是 `N`、`S`、`E` 或 `W` 之一。 初始时没有两艘舰船的坐标相同。换句话说，对于任何两艘不同的舰船 $i$ 和 $j$，它们的横坐标 $x_i$ 和 $x_j$ 不可能同时相等，纵坐标 $y_i$ 和 $y_j$ 也不可能同时相等。

对于每艘存活的战舰，单独输出一行，包含该舰船的编号 $i\ (1 \leq i \leq N)$。你可以按照任何顺序输出幸存舰船的编号。 如果没有存活的战舰，则输出为空。

**样例解释 1** 初始战舰分布如下图：  海战过程： - 第 $2$ 回合，战舰 $3$ 和 $4$ 在 $(4, 4)$ 处相撞。 - 第 $6$ 回合，战舰 $1$ 和 $5$ 在 $(6, 6)$ 处相撞，战舰 $2$ 和 $6$ 在 $(6, 8)$ 处相撞。 最终仅剩战舰 $7$ 存活。 **样例解释 2** 初始战舰分布如下图：  第 $2$ 回合，战舰 $1$、$3$、$4$ 在 $(2, 4)$ 处相撞，战舰 $2$ 和 $5$ 存活。 **数据范围与提示** 对于所有输入数据，满足： - $2 \leq N \leq 2 \cdot 10^5$ - $0 \leq x_i, y_i \leq 10^9\ (1 \leq i \leq N)$，且 $x_i, y_i$ 均为偶数 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :--: | :--: | :--: | | $1$ | $N = 2$ | $6$ | | $2$ | $N \leq 100, x_i, y_i \leq 100\ (1\leq i\leq n)$ | $12$ | | $3$ | $N \leq 100, x_i, y_i \leq 10^5\ (1\leq i\leq n)$ | $8$ | | $4$ | $N \leq 200$ | $11$ | | $5$ | $N \leq 5\,000$ | $9$ | | $6$ | $d_i\ (1 \leq i \leq N)$ 为 `S` 或 `E` | $30$ | | $7$ | 无附加限制| $24$ |