题目描述

在一条无限长的数轴上，有 $n$ 个机器人和 $m$ 个尖刺，每个都位于数轴的某个特定位置。第 $i$ 个机器人位于位置 $a_i$，第 $i$ 个尖刺位于位置 $b_i$。如果一个机器人碰到一个尖刺，它就会死亡。

共有 $k$ 条指令被传达给机器人，每条指令要么是向左移动一单位，要么是向右移动一单位。

对于每个 $i$（$1 \leq i \leq k$），输出在前 $i$ 条指令执行后，仍然存活的机器人数量。

输入格式

本题有多组数据

第一行输入一个整数 $t$ 表示测试数据组数。对于每一组数据：

• 第一行输入三个整数 $n,m,k$，分别表示机器人数量、尖刺数量和指令数。
• 第二行输入 $a_1,a_2,\ldots,a_n$ 表示机器人的初始位置。
• 第三行输入 $b_1,b_2,\ldots,b_m$ 表示尖刺的位置。
• 第四行包含一个长度为 $k$ 的字符串，表示传递给机器人的指令。每个字符为 $\texttt{L}$（向左移动一位）或 $\texttt{R}$（向右移动一位）。

输出格式

输出 $k$ 个整数，第 $i$ 个整数表示前 $i$ 条指令执行后存活的机器人数量。

3
2 1 3
0 1
2
LRR
2 3 3
2 4
1 3 5
LRL
3 2 3
1 3 7
9 6
RRL

2 2 1 
0 0 0 
3 2 2

提示

样例解释

对于第一个测试用例：

• 第一个机器人将依次移动到 $0 \rightarrow -1 \rightarrow 0 \rightarrow 1$，因此不会死亡。
• 第二个机器人将依次移动到 $1 \rightarrow 0 \rightarrow 1 \rightarrow 2$，所以在第三条指令执行后会死亡，因为 $2$ 处有尖刺。

对于第二个测试用例，两个机器人在移动一次后都会死亡。

数据范围

对于 $100\%$ 的数据满足：$1\leq t\leq 10^4$，$0\le a_i,b_i\leq 10^9$。保证所有测试用例中，$n, m, k$ 的总和不超过 $2 \cdot 10^5$。

额外约束：保证没有机器人和尖刺处于同一位置。

• 子任务 1（$30$ 分）：$n,m,k\leq 100$。
• 子任务 2（$30$ 分）：$n,k\leq 2000$。
• 子任务 3（$40$ 分）：无特殊限制。