有一个字符串 s,由大写拉丁字母组成。我们将其当前长度表示为|s|。在一次移动过程中,允许对其应用以下操作之一:
- INSERT pos ch — 在字符串 s 的 pos 位置插入字母 ch (1 ≤ pos ≤ |s| + 1, A ≤ ch ≤ Z)。字母 ch 成为字符串 s 的第 pos 个符号,此时字母移到一边并且字符串的长度增加 1。
- DELETE pos — 从字符串 s 中删除第一个字符 pos (1 ≤ pos ≤ |s|)。此时字母会移动到一起,并且字符串的长度减少 1。
- REPLACE pos ch — 将 s 行 pos 位置的字母替换为 ch (1 ≤ pos ≤ |s|, A ≤ ch ≤ Z)。此时字符串的长度不会改变。
你的任务是找出从 s 字符串中得到 t 字符串所需的最小移动次数。您还应该找到导致所需结果的操作顺序。
输入
第一行包含 s,第二行包含 t。这些行仅由大写拉丁字母组成,其长度为 1 到 1000 之间的正数。
输出
在第一行中打印给定操作序列中的移动次数 k。该数量应该是尽可能少的数量。然后打印 k 行,每行包含一个操作。按照上述格式打印操作。如果有多个解决方案,请打印其中任何一个。
示例
输入 #1
ABA ABBBA
输出 #1
2 INSERT 3 B INSERT 4 B
输入 #2
ACCEPTED WRONGANSWER
输出 #2
10 REPLACE 1 W REPLACE 2 R REPLACE 3 O REPLACE 4 N REPLACE 5 G REPLACE 6 A INSERT 7 N INSERT 8 S INSERT 9 W REPLACE 11 R