题目背景

在一个物理定律失常的平行宇宙里……

题目描述

一座新的研究设施刚刚建成。它被称为大型反强子对撞机（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 \ne E$)。字符串 $S$ 和 $E$ 只包含字符 A 和 P。

输出格式

对于每个测试用例，按以下格式输出。

如果无解，则输出一行一个字符串 -1。

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

1. "+P i" 表示对从左数第 $i$ 个粒子（$i \ge 1$）应用操作 1。该粒子必须是质子。
2. "+A i" 表示对从左数第 $i$ 个粒子（$i \ge 1$）应用操作 2。该粒子必须是反质子。
3. "-A i" 表示对 $a$ 个连续粒子应用操作 3，其中最左边的粒子是从左数的第 $i$ 个粒子（$i \ge 1$）。这些粒子必须是反质子。
4. "-P i" 表示对 $p$ 个连续粒子应用操作 4，其中最左边的粒子是从左数的第 $i$ 个粒子（$i \ge 1$）。这些粒子必须是质子。

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

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

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

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$ PAAAPAAAAA $\to$ PAAAAAPAAAAAAAAAAA。

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