题目背景

— s10

题目描述

平面上有 $n$ 个位置互不相同的刺。刺有上下左右这 $4$ 种朝向。

定义一个【阴间刺】（其实就是削过的 sf 刺）为满足以下条件的有序刺对 $(s_1,s_2,s_3)$：

• $s_1$ 朝右，$s_2$ 朝左，$s_3$ 朝上。
• $x(s_1)<x(s_2)\leqslant x(s_3)$。
• $y(s_2)>y(s_1)>y(s_3)$。
• $x(s_2)-x(s_1)\leqslant d$。

其中 $x(s)$ 和 $y(s)$ 分别表示刺 $s$ 的横坐标和纵坐标；$d$ 为 kid 的宽度，在单组测试点中为常量。

坐标系 $x$ 轴正方向为从左到右，$y$ 轴正方向为从下到上。

上图是 $d\geqslant 2$ 时两个阴间刺的例子。虽然第二个刺型中 s3 对 kid 的跳跃没有影响/oh

给出 $n$ 个刺的位置和朝向，请你告诉 kid 有多少（他跳不过去的）阴间刺。

显然朝下的刺在本题内是没有意义的。

输入格式

本题单测试点内有多组数据。

第一行仅两个正整数 $T,id$ 表示测试数据的数量和测试点编号。特别地，样例的 $id=0$。

对于每组测试点，第一行输入两个正整数 $n,d$，表示刺的数量和 kid 的宽度，接下来 $n$ 行每行两个整数 $x,y$ 和一个字符 $c$ 表示一个刺的位置和朝向：U 代表朝上，D 代表朝下，L 代表朝左，R 代表朝右。

输出格式

对于每组测试点，输出一行一个正整数表示阴间刺的数量。

4 0
3 1
2 1 U
1 2 R
2 3 L
3 1
4 1 U
1 2 R
3 4 L
6 4
2 1 U
1 2 R
3 2 U
2 3 L
1 3 R
2 4 L
8 9
4 5 L
1 4 R
3 4 L
2 3 R
1 2 R
3 2 U
4 2 U
3 1 U

1
0
4
6

见附件中的 s4/ex.in

见附件中的 s4/ex.out

提示

【数据范围】

本题采用捆绑测试。

$$\def\r{\cr\hline} \def\arraystretch{1.5} \begin{array}{c|c|c|c|c} \textbf{Subtask} & id= & {\sum n\leqslant} & \textbf{Other Constraints} & \textbf{Score}\r \textsf1 & 1\sim 7 & 3\times10^4 & n\leqslant 30 & 10 \r \textsf2 & 31\sim45 & 10^4 & - & 25 \r \textsf3 & 8\sim10,16\sim17 & 10^5 & d=10^9 & 20 \r \textsf4 & 18\sim20 & 3\times10^5 & d=1 & 10 \r \textsf5 & 11\sim15,21\sim30 & 3\times10^5 & - & 35 \r \end{array} $$

其中 $\sum n$ 表示单测试点内所有 $n$ 的总和。

对于 $100\%$ 的数据，$1\leqslant T\leqslant 2\times10^3$，$1\leqslant n\leqslant 3\times10^5$，$\sum n\leqslant 3\times10^5$，$1\leqslant d\leqslant 10^9$，$1\leqslant x,y\leqslant 10^9$，$(x,y)$ 互不相同，$c\in\{\texttt U, \texttt D, \texttt L, \texttt R \}$。

【提示】

$\textbf{Sub}{\textsf2}$ 的 $O(n^2\log n)$ 做法和 $O(n^2)$ 做法都可以想想，可能都有些提示性……？qwq

【样例 #1-1 & #1-2 解释】

见【题目描述】中两幅图。

注意 #1-2 中 $d=1$，所以 kid 可以简单地钻缝过去，不算阴间。

【样例 #1-3 解释】

$4$ 个阴间刺分别为：$\Big((1,3),(2,4),(2,1)\Big),\Big((1,2),(2,4),(2,1)\Big),\Big((1,2),(2,3),(2,1)\Big),\Big((1,3),(2,4),(3,2)\Big)$ 即 $(5,6,1),(2,6,1),(2,4,1),(5,6,3)$（数字代表刺的下标：$i$ 代表第 $i$ 个刺）。

【样例 #1-4 解释】

$6$ 个阴间刺分别为 $(2,1,7),(4,1,7),(4,3,6),(4,3,7),(4,3,8),(5,3,8)$。

【样例 #2】见附件，该样例除 $id=0$ 外满足 $\text{Subtask }\textsf1$ 的所有限制。