在此问题中,黑客被禁用。
有一个条带包含 $$$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$$$:末尾黑色单元格的数量;
- 在第二行中,按升序打印黑色单元格的标签。
示例
输入复制
53 2BAB2 53 4ABA1 4 9 105 2ABABB1 73 1BBA61 4A1 3 4 1000000000
输出复制
42 3 5 671 2 3 4 6 9 1071 2 3 5 6 7 932 4 651 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$$$。