问题描述：

给定两个字符串s1、s2,李华想在操作次数最少的前提下用尽可能少的代价将s1变成s2。
对字符串的操作有三种：
1. 将一个字符改为另一个字符，操作的代价为1;
2. 删除一个字符，操作的代价为2;
3. 插入一个字符，操作的代价为3;
对任给的两个字符串A和B，计算出将字符串A变换为字符串B的操作次数,并输出每次操作后的字符串。

输入：

第一行输入字符串s1
第二行输入字符串s2

输出：

第一行输出最少的操作次数n
接下来n行输出每次操作之后的字符串

Input

emdsic
efxaasi

Output

5
1:efmdsic
2:efxmdsic
3:efxadsic
4:efxaasic
5:efxaasi

数据范围：

对于50%的数据：s1、s2的长度<=10
对于60%的数据：s1、s2的长度<=100
对于80%的数据：s1、s2的长度<=500
对于100%的数据：s1、s2的长度<=1000

Hint

开始时字符串为：emdsic
第1次操作：在第一和第二个字母之间插入一个f，字符串变为：efmdsic
第2次操作：在第二和第三个字母之间插入一个x，字符串变为：efxmdsic
第3次操作：将第四个字母变为a，字符串变为：efxadsic
第4次操作：将第五个字母变为a，字符串变为：efxaasic
第5次操作：将第八个字母删除，字符串变为：efxaasi

Limitation

1s, 64M for each test case.