Ondra 最近被晋升为捷克海军大将。然而，当他终于认为自己有了一份稳定的工作时，政府宣布了包括解散海军在内的预算削减计划。

因此，Ondra 决定向政府展示捷克海军的重要性。他从间谍那里得知即将发生一场涉及四大舰队的海战。如果他能赢得这场战斗，无疑将是一次有力的证明。

不幸的是，捷克海军既没有军舰也没有海港。但如果 Ondra 的间谍能接管一些船只，他或许还有机会。要是他能知道哪些船只会在战斗中幸存下来就好了……

海战过程如下：最初，第 $i$ 艘船位于坐标 $(x_i, y_i)$，其中 $x_i$ 和 $y_i$ 均为偶数。此外，每艘船属于四个舰队之一：北方（Northern）、南方（Southern）、东方（Eastern）或西方（Western）。战斗按步骤进行。在每一步中：

• 首先，每艘船同时向其舰队对应的方向移动一个单位。
• 如果两艘或多艘船现在占据同一个方格，它们就会沉没并从地图上消失。

当不再可能发生碰撞时，战斗结束。幸存船只是指战斗结束后仍留在地图上的船只。

船只根据其舰队的方向移动。每个方向的移动会改变其坐标如下：

• 北方（Northern）—— $y$ 坐标减 1
• 南方（Southern）—— $y$ 坐标加 1
• 东方（Eastern）—— $x$ 坐标加 1
• 西方（Western）—— $x$ 坐标减 1

输入格式

第一行包含一个整数 $N$。接下来 $N$ 行，每行包含 $x_i, y_i$ 和 $d_i$，以空格分隔。整数 $x_i$ 和 $y_i$ 是第 $i$ 艘船的坐标。字符 $d_i$ 为 N、S、E 或 W，描述了第 $i$ 艘船所属舰队的方向。

没有两艘船的初始坐标相同。也就是说，对于船 $i$ 和 $j$ ($i \neq j$)，要么 $x_i \neq x_j$，要么 $y_i \neq 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. (6 分) $N = 2$
2. (12 分) $N \leq 100, x_i, y_i \leq 100$（对于每个 $1 \leq i \leq N$）
3. (8 分) $N \leq 100, x_i, y_i \leq 10^5$（对于每个 $1 \leq i \leq N$）
4. (11 分) $N \leq 200$
5. (9 分) $N \leq 5\,000$
6. (30 分) $d_i$ 仅为 S 或 E（对于每个 $1 \leq i \leq N$）
7. (24 分) 无附加限制