You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

海战游戏

有 $n$ 艘船参与海战。

最初，第 $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$ 是N, S, E或W中的一个，描述第i艘船的舰队方向。

保证最初任意两艘船坐标不一样。

输出格式

对于每艘幸存的船只，输出一个单独的行，包含整数i（1 ≤ i ≤ N）—— 船只的编号。从小到大输出。

如果没有幸存的船只，输出应该是空的。

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。

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

2
5

在第二步，船只1、3和4将在(2, 4)处相撞。船只2和5将幸存。

限制条件

• $2 \le N \le 2 × 10^5$
• $0 \le x_i, y_i \le 10^9$ 并且 $x_i, y_i$是偶数。

子任务

1. （6分）$N = 2$
2. （12分）$N \le 100, x_i, y_i \le 100$
3. （8分）$N \le 100, x_i, y_i \le 10^5$
4. （11分）$N \le 200$
5. （9分）$N \le 5000$
6. （30分）$d_i$ 是S或E中的一个
7. （24分）没有额外的限制条件