碰撞 2

题目描述

在 $xy$ 平面上有 $N$ 个人。第 $i$ 个人位于 $(X_i, Y_i)$。所有人的位置互不相同。

我们有一个长度为 $N$ 的、由 L 和 R 组成的字符串 $S$。

如果 $S_i =$ R,第 $i$ 个人面向右;如果 $S_i =$ L,第 $i$ 个人面向左。所有人同时开始朝各自面向的方向行走。这里,右和左分别对应 $x$ 轴的正方向和负方向。

当两个相向而行的人到达同一位置时,我们说发生了碰撞。如果所有人一直继续行走,是否会发生碰撞?

输入格式

输入按以下格式从标准输入给出:

N
X_1 Y_1
X_2 Y_2
⋮
X_N Y_N
S

输出格式

如果会发生碰撞,输出 Yes;否则,输出 No。

样例

3
2 3
1 1
4 1
RRL

Yes

这个输入对应题目描述中的例子。

如果所有人继续行走,第 $2$ 个人和第 $3$ 个人会发生碰撞。因此应输出 Yes。

2
1 1
2 1
RR

No

第 $1$ 个人和第 $2$ 个人朝相同的方向行走,因此永远不会碰撞。

10
1 3
1 4
0 0
0 2
0 4
3 1
2 4
4 2
4 4
3 3
RLRRRLRLRR

Yes

数据范围

• $2 \le N \le 2 \times 10^5$
• $0 \le X_i \le 10^9$
• $0 \le Y_i \le 10^9$
• 若 $i \neq j$,则 $(X_i, Y_i) \neq (X_j, Y_j)$。
• 所有 $X_i$ 和 $Y_i$ 均为整数。
• $S$ 是长度为 $N$ 的、由 L 和 R 组成的字符串。