题目描述

瓦夏非常喜欢参加信息学奥林匹克。他早已明白，自己最喜欢解决字符串相关的问题。最近发明的一种数据结构——回文树——给他留下了特别深刻的印象。事实证明，几乎任何字符串题都能用这个真正全能的数据结构解决，因为它甚至能在根本不存在回文的地方找到回文！

然而，瓦夏无论如何都没法让回文树不是去寻找回文，而是从字符串中创造回文。可他非常想这样做！同时，由于瓦夏非常珍惜遇到的字符串，他只想在任意位置添加字符，而不删除或修改原字符。请帮助他找到把普通字符串变成回文的方法。

输入格式

唯一一行包含一个非空字符串 $s$，由小写英文字母组成。其长度记为 $|s|$，不超过 $15000$。

输出格式

第一行输出一个整数 $a$，表示为了把字符串 $s$ 变成回文串，最少需要添加的字符数。第二行输出一个字符串 $t$，它是一个回文串，并且可以由 $s$ 添加你所给出的数量的字符得到。换言之，应满足 $|s|+a=|t|$。

样例

样例 1

ab

1
bab

样例 2

abba

0
abba

样例解释

回文串是指正着读和反着读完全相同的字符串。例如，a、abraarba 是回文串，而 ab 和 abracadabra 不是。

评分方式

测试由七组组成。只有通过某一组的所有测试以及所有前置测试组时，才能获得该组分数。

| 组别 | 测试点 | 分数 | 附加限制 $|s|$ | 说明 | | :--: | :----: | :--: | :-------------- | :------------------------- | | 0 | 1–2 | 0 | — | 样例测试 | | 1 | 3–12 | 20 | $|s| \le 4$ | 字符串只由 a 和 b 组成 | | 2 | 13–38 | 15 | $|s| \le 300$ | | | 3 | 39–51 | 15 | $|s| \le 1000$ | | | 4 | 52–61 | 20 | $|s| \le 5000$ | | | 5 | 62–72 | 15 | $|s| \le 10000$ | | | 6 | 73–82 | 15 | $|s| \le 15000$ | |