← 返回题目列表

Codeforces · 2150/A

A. 增量路径

中文机器翻译题面 查看原题
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$$$ 为白色。

有一个长度为$$$n$$$的字符串$$$s$$$,由$$$n$$$命令组成。对于按顺序从 $$$1$$$ 到 $$$n$$$ 的每个 $$$i$$$,一个人

  • 从单元格 $$$1$$$ 开始;
  • 执行字符串中的第一个 $$$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 \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$$$。