E. Роботизированная спешка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Существует бесконечно длинная числовая прямая.

На числовой прямой находятся $$$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 при отправке.

Пример
Входные данные
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$$$ находится шип.

Для второго набора входных данных оба робота погибнут после одного перемещения.