在一个物理定律完全失控的平行宇宙中……

一个新的研究设施刚刚建成。它被称为大型反强子对撞机（Large Antihadron Collider, LAC），是同类中最大的反粒子对撞机。反物理学家们渴望利用它来研究所谓的“常规物质”，它与反物质相似，只是电荷、宇称和时间反转。

在 LAC 的一次实验中，反物理学家成功地将两种粒子——反质子和质子——限制在一个容器中，粒子从左到右排列。我们可以用一个 1-索引的字符串来表示容器的状态。字符串的长度等于容器中粒子的数量，如果第 $i$ 个粒子是反质子，则字符串的第 $i$ 个字符为 A；如果是质子，则为 P。

利用 LAC 的奇异能量束，他们可以使用四种不同类型的操作来修改状态：

• 操作 1：选择一个特定的质子，然后在它的左侧和右侧各插入一个反质子。这相当于将状态字符串中对应的字符 P 替换为 APA。
• 操作 2：选择一个特定的反质子，然后在它的左侧和右侧各插入一个质子。这相当于将状态字符串中对应的字符 A 替换为 PAP。
• 操作 3：选择一个包含 $a$ 个反质子的连续子序列，并将它们移除。
• 操作 4：选择一个包含 $p$ 个质子的连续子序列，并将它们移除。

注意，操作 3 中的整数 $a$ 和操作 4 中的整数 $p$ 在输入中给出且是固定的。

这些操作可以以任意顺序执行任意次数，但每次只能执行一个操作。

初始状态由字符串 $S$ 表示。他们希望通过一系列操作将其转换为由字符串 $E$ 表示的目标状态。请确定这是否可行。如果可行，请找出将初始状态转换为目标状态的操作序列。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 10$)，表示测试用例的数量。接下来是 $t$ 个测试用例。每个测试用例由一行组成，包含两个整数 $a$ 和 $p$ ($5 \le a, p \le 20$) 以及两个字符串 $S$ 和 $E$ ($1 \le |S|, |E| \le 50, S \neq E$)。字符串 $S$ 和 $E$ 仅由字符 A 和 P 组成。

输出格式

对于每个测试用例，输出如下内容：

如果转换是不可能的，则单行输出 -1。

否则，在第一行输出一个整数 $k$，表示将初始状态转换为目标状态所需的操作次数。在接下来的 $k$ 行中，每行输出以下内容之一（不含引号）来描述一个操作：

1. "+P $i$"：对从左侧数第 $i$ 个粒子执行操作 1 ($i \ge 1$)。该粒子必须是质子。
2. "+A $i$"：对从左侧数第 $i$ 个粒子执行操作 2 ($i \ge 1$)。该粒子必须是反质子。
3. "-A $i$"：对从左侧数第 $i$ 个粒子开始的 $a$ 个连续粒子执行操作 3 ($i \ge 1$)。这些粒子必须是反质子。
4. "-P $i$"：对从左侧数第 $i$ 个粒子开始的 $p$ 个连续粒子执行操作 4 ($i \ge 1$)。这些粒子必须是质子。

这些操作按输出行的顺序执行，并且必须将初始状态转换为目标状态。

操作次数 $k$ 必须满足 $1 \le k \le 35\,000$。可以证明，如果初始状态可以转换为目标状态，则总存在满足此 $k$ 上界的操作序列。任何满足此 $k$ 上界的有效序列都将被接受。特别地，你不需要最小化 $k$ 的值。

样例

输入 1

4
13 10 PP PAAAAPAAAA
10 13 AAAAAAA PPPPPPP
7 8 PPAAAAAAAAP PPAP
8 9 PAPPPPPPPPP PPAP

输出 1

4
+P 2
+P 3
+P 4
+P 5
-1
1
-A 3
2
+A 2
-P 5

说明 1

在第一个测试用例中，状态字符串的操作序列为： PP $\to$ PAPA $\to$ PAAPAA $\to$ PAAAPAAA $\to$ PAAAAPAAAA。

在第四个测试用例中，状态字符串的操作序列为： PAPPPPPPPPP $\to$ PPAPPPPPPPPPP，然后 PPAPPPPPPPPPP $\to$ PPAP。