「CEOI2024」海战

题目描述

捷克海军司令官翁德拉刚刚晋升为大元帅，正享受着新职位的安稳，却突然被政府通知海军将被裁撤。

翁德拉决心证明捷克海军的重要性。他通过间谍得知，一场四国海军巨舰对决即将展开。如果能赢得这场战役，无疑能向政府有力地展示海军价值。

然而，捷克海军既无战舰也无港口。但翁德拉想到，如果他的间谍能夺取几艘参战舰艇，或许还有一线生机。关键是，如何预知哪些船能在这场海战中幸存下来呢？

海战规则如下：

• 战前，第 $i$ 艘战舰位于坐标 $(x_i, y_i)$ 处，其中 $x_i$ 和 $y_i$ 均为偶数。
• 每艘战舰隶属于北方、南方、东方或西方舰队之一。
• 海战分回合进行。每回合：
  • 每艘战舰同时向其所属舰队方向移动一格。
  • 如果两艘或以上战舰占据同一格，它们将相撞沉没，从海图上消失。
• 当不再发生碰撞时，海战结束。存活的战舰是指海战结束后仍留在海图上的战舰。

各舰队战舰的移动方向及坐标变化如下：

• 北方舰队（N）：$y$ 坐标减 $1$
• 南方舰队（S）：$y$ 坐标加 $1$
• 东方舰队（E）：$x$ 坐标加 $1$
• 西方舰队（W）：$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

输入

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

输出

7

解释

初始战舰分布如下图：

海战过程：

• 第 $2$ 回合，战舰 $3$ 和 $4$ 在 $(4, 4)$ 处相撞。
• 第 $6$ 回合，战舰 $1$ 和 $5$ 在 $(6, 6)$ 处相撞，战舰 $2$ 和 $6$ 在 $(6, 8)$ 处相撞。
• 最终仅剩战舰 $7$ 存活。

样例 2

输入

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

输出

5
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