CF56D.Changing a String

There is a string s, consisting of capital Latin letters. Let's denote its current length as |s|. During one move it is allowed to apply one of the following operations to it:

• INSERT pos ch — insert a letter ch in the string s in the position pos (1 ≤ pos ≤ |s| + 1, A ≤ ch ≤ Z). The letter ch becomes the pos-th symbol of the string s, at that the letters shift aside and the length of the string increases by 1.
• DELETE pos — delete a character number pos (1 ≤ pos ≤ |s|) from the string s. At that the letters shift together and the length of the string decreases by 1.
• REPLACE pos ch — the letter in the position pos of the line s is replaced by ch (1 ≤ pos ≤ |s|, A ≤ ch ≤ Z). At that the length of the string does not change.

Your task is to find in which minimal number of moves one can get a t string from an s string. You should also find the sequence of actions leading to the required results.

给定一个由大写拉丁字母组成的字符串 $s$。设其当前长度为 $|s|$。在一次操作中，允许对字符串执行以下操作之一：

• INSERT pos ch —— 在字符串 $s$ 的第 pos 个位置插入字符 ch（其中 $1 \leq \textit{pos} \leq |s| + 1$，且 $A \leq \textit{ch} \leq Z$）。插入后，字符 ch 成为字符串 $s$ 的第 pos 个字符，原位置及其后的字符向后移动一位，字符串长度增加 $1$。
• DELETE pos —— 删除字符串 $s$ 中第 pos 个位置的字符（其中 $1 \leq \textit{pos} \leq |s|$）。删除后，其后的字符向前移动一位，字符串长度减少 $1$。
• REPLACE pos ch —— 将字符串 $s$ 中第 pos 个位置的字符替换为 ch（其中 $1 \leq \textit{pos} \leq |s|$，且 $A \leq \textit{ch} \leq Z$）。该操作不改变字符串长度。

你的任务是求出将字符串 $s$ 变为字符串 $t$ 所需的最少操作次数，并同时输出达成该目标的一组具体操作序列。

The first line contains s, the second line contains t. The lines consist only of capital Latin letters, their lengths are positive numbers from 1 to 1000.

第一行包含字符串 $s$，第二行包含字符串 $t$。每行仅由大写拉丁字母组成，其长度均为 $1$ 至 $1000$ 之间的正整数。

In the first line print the number of moves k in the given sequence of operations. The number should be the minimal possible one. Then print k lines containing one operation each. Print the operations in the format, described above. If there are several solutions, print any of them.

第一行输出给定操作序列中的移动次数 $k$。该数值应为可能的最小值。随后输出 $k$ 行，每行包含一个操作。操作格式需遵循上述描述。若存在多种解法，输出任意一种即可。