A8013 | 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.

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$ .

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.