考虑一个由小写英文字母组成的排列：$P = \{p_1, p_2, \dots, p_{26}\}$。利用 $P$，你可以生成以下字符串序列：

$$S_1 = p_1$$ $$S_2 = S_1 + p_2 + S_1$$ $$S_3 = S_2 + p_3 + S_2$$ $$\vdots$$ $$S_{26} = S_{25} + p_{26} + S_{25}$$

显而易见，$S_{26}$ 的长度为 $2^{26} - 1$ 个字符。$S_{26}$ 的开头形如 $p_1 p_2 p_1 p_3 p_1 p_2 p_1 \dots$。

给你一个由小写英文字母组成的字符串 $T$。对于一个固定的排列 $P$，你可以得到 $S_{26}$，然后将 $T$ 中的某些字母替换为其他字母，使得修改后的字符串成为 $S_{26}$ 的一个子串。你的目标是通过选择合适的排列 $P$，来最小化必须在 $T$ 中替换的字母数量。

输入格式

输入仅一行，包含一个由小写英文字母组成的字符串 $T$（$1 \le |T| \le 20\,000$）。

输出格式

第一行输出需要替换的最小字母数量。

第二行输出修改后的子串在字符串 $S_{26}$ 中开始的位置（下标从 1 开始）。

第三行输出排列 $P$（作为一个长度为 26 的字符串）。

样例

输入样例 1

baca

输出样例 1

0
2
abcdefghijklmnopqrstuvwxyz

输入样例 2

bcdbaaac

输出样例 2

3
2
cbdaefghijklmnopqrstuvwxyz