SP7851 JZPSTA - Stacks of Zippy

最近，Zippy 拿到了四个栈，分别是 A、B、C 和 D。开始时，栈 A 中有 $n$ 个元素，这些元素是 $1$ 到 $n$ 的一个排列，而栈 B、C 和 D 则都是空的。Zippy 可以执行以下四种操作： - 操作 a：将栈 A 的顶部元素移动到栈 B（前提是栈 A 非空） - 操作 b：将栈 B 的顶部元素移动到栈 D（前提是栈 B 非空） - 操作 c：将栈 A 的顶部元素移动到栈 C（前提是栈 A 非空） - 操作 d：将栈 C 的顶部元素移动到栈 D（前提是栈 C 非空） Zippy 一共可以进行 $2 \times n$ 次操作。经过这些操作后，栈 D 中应该正好有 $n$ 个元素。然后，他一次从栈 D 中取出顶部元素。如果取出的第一个元素是 $n$，接着是 $n-1$，一直到最后一个元素是 $1$，Zippy 会非常开心。同时，他也希望所采纳的操作序列在字典序上是最小的。

第一行是一个整数 $t$，表示测试用例的数量。 接下来的 $t$ 个测试用例中，每个测试用例的第一行是一个整数 $n$，表示栈 A 中的元素个数。第二行包含 $n$ 个整数，由空格分隔，表示栈 A 从顶到底的元素序列。 可以保证所有测试用例中 $n$ 值的总和不超过 $200,000$，且每个 $n$ 的值都不超过 $100,000$。

对于每个测试用例，输出一行，表示字典序最小的操作序列。操作序列由 `a`、`b`、`c` 和 `d` 四种字母组成。

- $1 \le t \le 100$ - $1 \le n \le 100,000$ - $\sum n \le 200,000$ **本翻译由 AI 自动生成**