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.
import sys
from array import array  # noqa: F401


def input():
    return sys.stdin.buffer.readline().decode('utf-8')


s, t = input().rstrip(), input().rstrip()
n, m = len(s), len(t)

dp = [[10**9] * (m + 2) for _ in range(n + 2)]
dp[n][m] = 0
prev = [[(-1, -1)] * (m + 2) for _ in range(n + 2)]

for i in range(n, -1, -1):
    for j in range(m, -1, -1):
        if i < n and j < m and dp[i][j] > dp[i + 1][j + 1] + (0 if s[i] == t[j] else 1):
            dp[i][j] = dp[i + 1][j + 1] + (0 if s[i] == t[j] else 1)
            prev[i][j] = (i + 1, j + 1)
        if i < n and dp[i][j] > dp[i + 1][j] + 1:
            dp[i][j] = dp[i + 1][j] + 1
            prev[i][j] = (i + 1, j)
        if j < n and dp[i][j] > dp[i][j + 1] + 1:
            dp[i][j] = dp[i][j + 1] + 1
            prev[i][j] = (i, j + 1)

i, j = 0, 0
ans = []
while i < n or j < m:
    ti, tj = prev[i][j]
    if i + 1 == ti and j + 1 == tj:
        if s[i] != t[j]:
            ans.append(f'REPLACE {j+1} {t[j]}')
    elif i + 1 == ti:
        ans.append(f'DELETE {j+1}')
    elif j + 1 == tj:
        ans.append(f'INSERT {j+1} {t[j]}')
    i, j = ti, tj


sys.stdout.buffer.write((str(len(ans)) + '\n' + '\n'.join(ans)).encode('utf-8'))
