CF2150A Incremental Path

[Rymdkraft - Rymdsylt](https://soundcloud.com/rymdkraft/rymdsylt) ⠀ 本题不允许使用 Hack。 有一条包含 $10^9$ 个格子的带子，这些格子按 $1$ 到 $10^9$ 编号。每个格子可以是黑色或白色。起初，有 $m$ 个不同的格子 $a_1, a_2, \ldots, a_m$ 是黑色，其余的都是白色。 如果有人当前位于格子 $x$，他可能会被给出以下两种指令之一： - $\texttt{A}$：跳到下一个格子，即格子 $x+1$； - $\texttt{B}$：跳到下一个白色格子，即最小的 $y > x$，满足格子 $y$ 是白色。 有一串长度为 $n$ 的命令字符串 $s$，包含 $n$ 个指令。对于每一个 $i$ 从 $1$ 到 $n$，一名"参与者"进行如下操作： - 从格子 $1$ 出发； - 按顺序执行 $s$ 的前 $i$ 个命令； - 将最后到达的格子涂黑（如果本来已经是黑色，则保持不变）。 你需要回答，最终哪些格子是黑色的，并按升序输出这些格子的编号。

每个测试点包含多组测试数据。第一行为测试用例数 $t$（$1 \le t \le 10^4$）。随后每组测试用例如下： 每个测试用例第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 10^5$，$1 \leq m \leq 10^5$），分别表示命令数量和初始黑色格子的数量。 第二行是一个长度为 $n$ 的字符串 $s$，由字符 $\texttt{A}$ 和 $\texttt{B}$ 组成，表示命令序列。 第三行包含 $m$ 个正整数 $a_1, a_2, \ldots, a_m$（$1 \leq a_1 < a_2 < \ldots < a_m \leq 10^9$），表示初始为黑色的格子的编号。 保证所有测试用例中 $n$ 的总和不超过 $10^5$，$m$ 的总和不超过 $10^5$。

对于每个测试用例，输出两行： - 第一行输出一个整数 $k$，表示最后黑色格子的数量； - 第二行输出这 $k$ 个黑色格子的编号，升序排列。

在第一个测试用例中，最初黑色格子为 $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$ 号格子。 由 ChatGPT 5 翻译