P13615 [ICPC 2024 APC] Antiparticle Antiphysics

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

一座新的研究设施刚刚建成。它被称为大型反强子对撞机（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$ 的值。

**样例解释 #1** 在第一个测试用例中，状态字符串的操作序列为 `PP` $\to$ `PAPA` $\to$ `PAAPAA` $\to$ `PAAAPAAAAA` $\to$ `PAAAAAPAAAAAAAAAAA`。 在第四个测试用例中，状态字符串的操作序列为 `PAPPPPPPPPP` $\to$ `PPAPPPPPPPPPP`，然后 `PPAPPPPPPPPPP` $\to$ `PPAP`。