remove

题目描述

有一个字符集为小写字母的字符串 $S$，你需要通过以下方法构造出这个串：

第一步：先构造若干回文串，并将其依次拼接，拼出的串记为 $S'$。

第二步：重复进行若干次：选择 $S'$ 中两个相邻且相同的字符，一起消除。

最终需要使得 $S'=S$。

你需要给出构造方案，并最小化第一步中使用的回文串个数。

为了保证输出量，还要求每个回文串串长 $\le 2|S|$，可以证明这个限制不会改变回文串最小使用个数。

输入格式

输入一个字符串 $S$。

输出格式

第一行输出一个数 $k$ 表示使用的回文串数。

接下来 $k$ 行，每行输出一个回文串，表示按输出顺序，从左到右拼接的字符串。

最后输出一个字符串，长度为回文串长度之和，由三种字符 $"\texttt{().}"$ 构成，一对匹配的左右括号即表示这两个位置的字符进行了一次消除。

根据题目要求，还需满足，一对匹配的左右括号对应字符相同，且其区间中不能存在字符 $"\texttt{.}"$。所有 $"\texttt{.}"$ 对应字符构成的字符序列应等于 $S$，而所有括号应匹配。

输入 #1

abac

输出 #1

2
aba
c
....

输入 #2

abbaa

输出 #2

1
abbabba
....().

说明/提示

大样例只给了最小回文串个数，方案合法性请自行检查。

对于所有数据满足：$|S| \le 500$。

子任务 1（10分）：$S$ 可以通过操作中的第二步消为空串。

子任务 2（20分）：$S$ 仅由 $a,b$ 构成。

子任务 3（20分）：$|S| \le 6$。

子任务 4（30分）：$S$ 中相邻字符不同。

子任务 5（20分）：无特殊性质。