Milica 有一个长度为 $$$n$$$ 的字符串 $$$s$$$,仅包含字符 A 和 B。她想要修改 $$$s$$$,使其恰好包含 B 的 $$$k$$$ 实例。在一个操作中,她可以执行以下操作:
- 选择一个整数 $$$i$$$ ($$$1 \leq i \leq n$$$) 和一个字符 $$$c$$$ ($$$c$$$ 等于 A 或 B)。
- 然后,将字符串 $$$s$$$ 的前 $$$i$$$ 字符(即字符 $$$s_1、s_2、\ldots、s_i$$$)替换为 $$$c$$$。
Milica 不想执行太多操作,以免浪费太多时间。
她要求你找出修改 $$$s$$$ 所需的最少操作数,使其恰好包含 B 的 $$$k$$$ 个实例。她还希望你找到这些操作(即在每个操作中选择的整数 $$$i$$$ 和字符 $$$c$$$)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 500$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$3 \leq n \leq 100$$$, $$$0 \leq k \leq n$$$) - 字符串 $$$s$$$ 的长度以及 B Milica 最后希望出现在 $$$s$$$ 中的字符数。
每个测试用例的第二行包含长度为$$$n$$$的字符串$$$s$$$,仅由字符A和B组成。
输出
对于每个测试用例,在第一行输出一个整数 $$$m$$$ — Milica 应该执行的最小操作数。
在接下来的 $$$m$$$ 行的第 $$$j$$$ 行中,输出一个整数 $$$i$$$ ($$$1 \le i \le n$$$) 和一个字符 $$$c$$$ ($$$c$$$ 是 'A' 或 'B') – 第 $$$j$$$ 操作的参数,如语句中所述。
如果存在多个具有最少可能运算次数的解,则输出其中任何一个。
示例
输入 #1
5 5 2 AAABB 5 3 AABAB 5 0 BBBBB 3 0 BAA 10 3 BBBABBBBAB
输出 #1
0 1 1 B 1 5 A 1 2 A 1 6 A
注意
在第一个测试用例中,$$$s$$$ 中已经有 $$$2$$$ 字符 B,因此 Milica 不必执行任何操作。
在第二个测试用例中,在一次操作中在 $$$s$$$ 中实现 $$$3$$$ 字符 B 的唯一方法是在第一个操作中用 B 替换 $$$s$$$ 的第一个字符:AABAB $$$\rightarrow$$$ BABAB。
在第三个测试用例中,在一次操作中在 $$$s$$$ 中实现 $$$0$$$ 字符 B 的唯一方法是在第一个操作中将 $$$s$$$ 的前 $$$5$$$ 字符替换为 A:BBBBB $$$\rightarrow$$$ AAAAA。
在第四个测试用例中,在一次操作中实现 $$$s$$$ 中的 $$$0$$$ 字符 B 的方法之一是在第一次操作中将 $$$s$$$ 的前 $$$2$$$ 字符替换为 A:BAA $$$\rightarrow$$$ AAA。请注意,“1 A”和“3 A”也是正确的一次操作解决方案。