Background

有一条无限长的数轴。

数轴上有 $n$ 个机器人和 $m$ 个尖刺，每个都位于数轴上的某个具体位置。第 $i$ 个机器人位于位置 $a_i$，第 $i$ 个尖刺位于位置 $b_i$。如果机器人碰到尖刺，它就会“阵亡”。

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

对于每个 $i$（共 $1 \le i \le k$ 个），请输出在执行完前 $i$ 条指令后，还有多少机器人幸存。

Format

Input

第一行输入一个整数 $t$（范围 $1 \le t \le 10^4$）——测试用例的数量。

每个测试用例第一行包含三个整数 $n, m, k$（范围 $1 \le n, m, k \le 2 \cdot 10^5$）——机器人数量、尖刺数量和指令数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（范围 $0 \le a_i \le 10^9$）——机器人所在的位置。保证这些位置两两不同。

第三行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$（范围 $0 \le b_i \le 10^9$）——尖刺所在的位置。保证这些位置两两不同。

第四行是长度为 $k$ 的字符串，表示传给机器人的指令。每个字符是 L（向左移动）或 R（向右移动）。

保证所有测试用例中 $n, m, k$ 的总和不超过 $2 \cdot 10^5$。

额外说明： 保证机器人和尖刺不会出现在同一个位置。

Output

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

Samples

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

Limitation

对于 60% 的数据，保证 $1 \leq \sum{n}, \sum{k} \leq 1000$