描述

魔板是一个长度为 $8$ 的字符串，初始时放着 $1\sim 8$ 的一个排列。下面定义三种操作：

我们把长度为 $8$ 的字符串 $s_1s_2s_3s_4s_5s_6s_7s_8$ 想象成 $2$ 行 $4$ 列：

$$\begin{matrix} s_1 & s_2 & s_3 & s_4 \\ s_5 & s_6 & s_7 & s_8 \end{matrix} $$

• 操作 A：上下两行整体互换。即 ABCDEFGH $\to$ EFGHABCD。
• 操作 B：每一行各自循环右移 1 位（最后一个字符移到这一行的最前面）。即 ABCD $\to$ DABC，EFGH $\to$ HEFG。合起来 ABCDEFGH $\to$ DABCHEFG。
• 操作 C：中间 4 个数字（第 3 $\sim$ 6 位，即下标 2 $\sim$ 5）循环左移 1 位。即 12345678 $\to$ 12456378（位置 2、3、4、5 的值由 3,4,5,6 变成 4,5,6,3）。

给定一个由 $1\sim 8$ 组成的初始字符串，请你求出：

1. 最少经过多少次操作，能从初始字符串到达目标字符串 12345678；
2. 达到目标所需的最短操作序列（输出为一个大写字母组成的字符串，每个字符依次是 A、B、C 中的一种）。

输入格式

输入共一行，是一个由数字 1–8 各出现一次组成的长度为 $8$ 的字符串。

输出格式

输出共一行。若可达，先输出最短操作序列，再输出一个空格，再输出操作次数；若不可达，输出 -1。

操作序列按字典序 A < B < C 的顺序输出最短的那一条；当多种最短路径长度相同时，输出字典序最小的那条。

样例

样例输入 1

12345678

样例输出 1

0

解释：初始即为目标，步数为 0，序列为空，按格式输出 0。

样例输入 2

23416785

样例输出 2

B 1

解释：23416785 通过一次操作 B（每行循环右移 1 位）即可变成 12345678。

样例输入 3

56781234

样例输出 3

A 1

解释：56781234 通过一次操作 A（上下两行互换）即可变成 12345678。