A. Инкрементальный путь
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Rymdkraft - Rymdsylt
⠀

В этой задаче отключены взломы.

Существует полоса, содержащая $$$10^9$$$ ячеек, пронумерованных от $$$1$$$ до $$$10^9$$$. Каждая ячейка либо черная, либо белая. Изначально $$$m$$$ различных ячеек $$$a_1, a_2, \ldots, a_m$$$ черные, а остальные — белые.

Если человек находится в какой-либо ячейке $$$x$$$, ему могут быть даны два типа команд:

  • $$$\texttt{A}$$$: прыгнуть в следующую ячейку, то есть в ячейку $$$x + 1$$$;
  • $$$\texttt{B}$$$: прыгнуть в следующую белую ячейку, то есть в минимальную ячейку $$$y \gt x$$$, такую что ячейка $$$y$$$ — белая.

Существует строка $$$s$$$ длиной $$$n$$$, состоящая из $$$n$$$ команд. Для каждого $$$i$$$ от $$$1$$$ до $$$n$$$ по порядку, человек

  • начинает с ячейки $$$1$$$;
  • выполняет первые $$$i$$$ команд из строки;
  • окрашивает последнюю посещенную ячейку в черный цвет (если она уже была черной, она остается черной).

Вам интересно, какие ячейки окажутся черными в конце процесса. Выведите их в порядке возрастания.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n \leq 10^5$$$, $$$1 \leq m \leq 10^5$$$) — количество команд и количество черных ячеек в начале.

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длиной $$$n$$$, состоящую из символов $$$\texttt{A}$$$ и $$$\texttt{B}$$$, представляющих команды.

Третья строка каждого набора входных данных содержит $$$m$$$ целых чисел $$$a_1, a_2, \ldots, a_m$$$ ($$$1 \leq a_1 \lt a_2 \lt \ldots \lt a_m \leq 10^9$$$) — начальные черные ячейки.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$, и что сумма $$$m$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

Выходные данные

Для каждого набора входных данных выведите две строки:

  • в первой строке выведите одно целое число $$$k$$$: количество черных ячеек в конце;
  • во второй строке выведите номера чёрных ячеек в порядке возрастания.
Пример
Входные данные
5
3 2
BAB
2 5
3 4
ABA
1 4 9 10
5 2
ABABB
1 7
3 1
BBA
6
1 4
A
1 3 4 1000000000
Выходные данные
4
2 3 5 6 
7
1 2 3 4 6 9 10 
7
1 2 3 5 6 7 9 
3
2 4 6 
5
1 2 3 4 1000000000
Примечание

В первом наборе входных данных изначально единственные черные ячейки — это $$$2$$$ и $$$5$$$.

Человек $$$1$$$:

  • начинает с ячейки $$$1$$$;
  • выполняет команду $$$\texttt{B}$$$, переходя к следующей белой ячейке ($$$3$$$);
  • окрашивает ячейку $$$3$$$ в черный цвет.

Человек $$$2$$$:

  • начинает с ячейки $$$1$$$;
  • выполняет команду $$$\texttt{B}$$$, переходя к следующей белой ячейке ($$$4$$$);
  • выполняет команду $$$\texttt{A}$$$, переходя к следующей ячейке ($$$5$$$);
  • окрашивает ячейку $$$5$$$ в черный цвет (она уже была черной, поэтому остается черной).

Человек $$$3$$$:

  • начинает с ячейки $$$1$$$;
  • выполняет команду $$$\texttt{B}$$$, переходя к следующей белой ячейке ($$$4$$$);
  • выполняет команду $$$\texttt{A}$$$, переходя к следующей ячейке ($$$5$$$);
  • выполняет команду $$$\texttt{B}$$$, переходя к следующей белой ячейке ($$$6$$$);
  • окрашивает ячейку $$$6$$$ в черный цвет.

В конце черные ячейки: $$$\{2, 3, 5, 6\}$$$.

Во втором наборе входных данных три человека оказываются в ячейках $$$2$$$, $$$3$$$ и $$$6$$$ соответственно.