**题目译自 [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$
## Input
第一行输入一个整数 $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$ 也不可能同时相等。
## Output
对于每艘存活的战舰，单独输出一行，包含该舰船的编号 $i\ (1 \leq i \leq N)$。你可以按照任何顺序输出幸存舰船的编号。
如果没有存活的战舰，则输出为空。
[samples]
## Note
**样例解释 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$ |