题目描述

小信正在调试一台智能移动机器人，准备进行一场路径测试。这台机器人的初始状态是：位于二维平面的原点 $(0,0)$，电量为 $h$。测试区域内还放置了 $m$ 块的电池，每块电池有唯一的位置 $(x_i, y_i)$，并且每个电池只能给机器人补充一次电量。

机器人需要按预设的指令序列完成 $n$ 次移动，每次移动的规则如下：
移动前，机器人的位置是 $(x,y)$。移动时，它会先消耗 $1$ 点电量，再根据指令方向移动：

• 指令为 R 时，移到 $(x+1,y)$；
• 指令为 L 时，移到 $(x-1,y)$；
• 指令为 U 时，移到 $(x,y+1)$；
• 指令为 D 时，移到 $(x,y-1)$。

移动结束后：

1. 若此时电量为负数，机器人会立刻停止运行，无法继续后续移动；
2. 若此时位置有电池，且当前电量小于 $k$，机器人会自动将电量充至 $k$。

请你判断，这台机器人能否顺利完成所有 $n$ 次移动？

输入格式

每组测试包含多个测试用例。第一行包含整数 $t$，表示测试用例数。
每组数据第一行包含四个整数 $n, m, h, k$，分别表示移动次数、电池数量、初始电量、电池电量。
第二行一个长度为 $n$ 的字符串 $S$，表示机器人的移动指令。
接下来 $m$ 行，每行两个整数 $x_i, y_i$，表示电池的位置。
本题输入数据量较大，请使用高效的读入方式

输出格式

对于每组数据，如果机器人能完成 $n$ 次移动，输出 Yes，否则输出 No。

样例

Input 1

2
5 3 2 2
URULL
1 1
0 2
1 2
5 2 2 2
URULL
1 1
-1 2

Output 1

Yes
No

数据范围

对于 $20\%$ 的数据，满足 $1 \leq n, m \leq 10^3$。
对于 $100\%$ 的数据，$1 \leq t \leq 20$，$1 \leq n, m, h, k \leq 2 \times 10^5$，$1 \leq |x_i|, |y_i| \leq 2 \times 10^5$，并且字符串 $S$ 只包含 L, R, U, D。

样例解释

样例的第一个测试点：
初始位置 $(0,0)$，初始电量为 $2$ 进行 $5$ 次移动：
第 $1$ 次指令 U：到达位置 $(0,1)$，剩余电量 $1$；
第 $2$ 次指令 R：到达位置 $(1,1)$，剩余电量 $0$，当前位置有电池，充电后电量为 $2$；
第 $3$ 次指令 U：到达位置 $(1,2)$，剩余电量 $1$；
第 $4$ 次指令 L：到达位置 $(0,2)$，剩余电量 $0$，当前位置有电池，充电后电量为 $2$；
第 $5$ 次指令 L：到达位置 $(-1,2)$，剩余电量 $1$；
顺利完成 $5$ 次移动，输出 Yes。

样例的第二个测试点：
可以发现第 $4$ 次指令后电量为 $0$，此时消耗电量后机器人停止运行，因此输出 No。