时空限制

1S/256M

题目描述

一片水域可以看作一个平面直角坐标系。水域中散落着 $n$ 碗美味的白饭，第 $i$ 碗白饭位于坐标 $(x_i, y_i)$ 处。

水域中有一只爱吃白饭的大肥鱼，它最初位于坐标 $(x_0, y_0)$，并且正面向方向 $d$。

若一碗白饭与大肥鱼位于同一条水平或竖直直线上，并且处于大肥鱼当前朝向的一侧，则称这碗白饭位于大肥鱼的前方。

大肥鱼有一套固定的“干饭”规则：

1. 大肥鱼沿当前方向直线游动。若前方有尚未被吃掉的白饭，它会游到距离最近的那一碗所在的位置并将其吃掉，此时大肥鱼的位置变为该碗白饭原来的位置；若前方没有白饭，游动直接结束。
2. 吃掉一碗白饭后，大肥鱼必须选择向左或向右转 90 度，然后继续按上述规则寻找下一碗白饭。

被吃掉的白饭会从平面上消失，不再影响之后的游动。

你可以决定大肥鱼每次吃完白饭后是向左转还是向右转。求大肥鱼最多能够吃掉多少碗白饭。

格式

输入格式

第一行包含一个正整数 $n$，表示白饭的数量。

第二行包含两个整数 $x_0,y_0$ 和一个字符 $d$，分别表示大肥鱼的初始位置和初始方向。字符 $d$ 为 U、D、L、R 之一，依次表示向上、向下、向左、向右。

接下来 $n$ 行，第 $i$ 行包含两个整数 $x_i,y_i$，表示第 $i$ 碗白饭的位置。

输出格式

输出一行一个整数，表示大肥鱼最多能够吃掉的白饭数量。

样例

样例输入 #1

2
0 0 U
0 1
0 2

样例输出 #1

1

样例解释 #1

大肥鱼首先吃掉位于 $(0,1)$ 的白饭。此后它必须向左或向右转 $90$ 度，不能继续向上游动，因此无法吃掉位于 $(0,2)$ 的白饭。

样例输入 #2

6
0 0 U
0 2
-1 2
-1 3
-2 3
-2 -1
-2 -3

样例输出 #2

5

数据规模

注意：你只有通过了该题目的所有测试点，才能获得分数。

对于 $100\%$ 的数据，满足 $1\le n\le 20$，$|x_0|,|y_0|,|x_i|,|y_i|\le 10^9$；所有白饭的位置两两不同，且没有白饭位于 $(x_0,y_0)$。