存在一条无限长的数轴。
在数轴上,有 $$$n$$$ 个机器人和 $$$m$$$ 尖峰,每个尖峰位于数轴上的特定点。第 $$$i$$$ 个机器人位于位置 $$$a_i$$$,第 $$$i$$$ 个尖峰位于位置 $$$b_i$$$。如果机器人碰到尖刺,它就会死亡。
$$$k$$$指令被传送到机器人,每个指令要么向左移动一个单位,要么向右移动一个单位。
对于每个值 $$$i$$$ ($$$1 \leq i \leq k$$$),输出在处理第一个 $$$i$$$ 指令后仍然存活的机器人数量。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含三个整数 $$$n, m, k$$$ ($$$1 \le n, m, k \le 2 \cdot 10^5$$$) — 分别是机器人、尖峰和指令的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — 机器人的位置。保证 $$$a$$$ 的所有元素都是不同的。
第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$0 \le b_i \le 10^9$$$) — 尖峰的位置。保证 $$$b$$$ 的所有元素都是不同的。
第四行包含长度为 $$$k$$$ 的字符串 — 传输到机器人的指令。每个字符要么是$$$\texttt{L}$$$,表示向左移动的指令,要么是$$$\texttt{R}$$$,表示向右移动的指令。
保证所有测试用例中每个 $$$n, m, k$$$ 的总和不超过 $$$2 \cdot 10^5$$$。
附加约束:保证同一位置没有机器人和尖刺。
输出
输出 $$$k$$$ 个整数,其中第 $$$i$$$ 个整数表示在处理第一个 $$$i$$$ 指令后有多少机器人处于活动状态。
对于 Python 用户,请确保在提交时选择 PyPy3 / PyPy2(取决于您使用的 Python 版本)而不是 Python3 或 Python2。
示例
输入复制
32 1 30 12LRR2 3 32 41 3 5LRL3 2 31 3 79 6RRL
输出复制
2 2 10 0 03 2 2
注意
对于第一个测试用例:
- 第一个机器人会移动到位置$$$0 \rightarrow -1 \rightarrow 0 \rightarrow 1$$$,所以它不会死。
- 第二个机器人将移动到位置 $$$1 \rightarrow 0 \rightarrow 1 \rightarrow 2$$$,因此在处理第三条指令后它将死亡,因为位置 $$$2$$$ 处有一个尖峰。
对于第二个测试用例,两个机器人都会在移动一次后死亡。