题目描述

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

现在向所有机器人发送 $k$ 条指令，每条指令要么让机器人向左移动 $1$ 个单位，要么向右移动 $1$ 个单位。

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

输入格式

第一行一个整数 $t$，表示测试组数。

每组测试数据第一行包含三个整数 $n,m,k$，分别表示机器人数量、尖刺数量和指令数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示机器人的位置。保证所有 $a_i$ 两两不同。

第三行包含 $m$ 个整数 $b_1,b_2,\ldots,b_m$，表示尖刺的位置。保证所有 $b_i$ 两两不同。

第四行包含一个长度为 $k$ 的字符串，字符为 L 或 R，分别表示向左或向右移动一个单位。

保证所有测试数据的 $n$、$m$、$k$ 之和分别都不超过 $2\cdot 10^5$。额外保证不存在机器人和尖刺初始位于同一点。

输出格式

对于每组测试数据，输出 $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\to -1\to 0\to 1$，不会死亡；第二个机器人移动轨迹为 $1\to 0\to 1\to 2$，在第三条指令后碰到位置 $2$ 的尖刺而死亡。

第二组测试数据中，两个机器人第一次移动后都会死亡。

数据范围

• $1 \le t \le 10^4$
• $1 \le n,m,k \le 2\cdot 10^5$
• $0 \le a_i,b_i \le 10^9$
• 所有 $a_i$ 两两不同，所有 $b_i$ 两两不同
• 初始时不存在机器人和尖刺位于同一点
• 所有测试数据的 $n$、$m$、$k$ 之和分别都不超过 $2\cdot 10^5$

来源

Codeforces Round 1074 (Div. 4), Problem E - The Robotic Rush