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.
s = input()
t = input()
dp = [[-1 for j in range(1001)] for i in range(1001)]

def solve(i: int, j: int) -> int:
    if i == len(s):
        return len(t) - j
    if j == len(t):
        return len(s) - i
    if dp[i][j] != -1:
        return dp[i][j]
    if s[i] == t[j]:
        dp[i][j] = solve(i+1, j+1)
    else:
        dp[i][j] = 1 + min(solve(i+1, j), solve(i, j+1), solve(i+1, j+1))
    return dp[i][j]

def insertChar(idx: int, c: str) -> None:
    print(f"INSERT {idx} {c}")

def replaceChar(idx: int, c: str) -> None:
    print(f"REPLACE {idx} {c}")

def deleteChar(idx: int) -> None:
    print(f"DELETE {idx}")

delta = 0

def backtrack(i: int, j: int) -> None:
    global delta
    if i == len(s):
        for x in range(j, len(t)):
            insertChar(i+delta+1, t[x])
            delta += 1
        return
    if j == len(t):
        for x in range(i, len(s)):
            deleteChar(x+delta+1)
            delta -= 1
        return
    if s[i] == t[j]:
        backtrack(i+1, j+1)
    else:
        replace = 1 + solve(i+1, j+1)
        add = 1 + solve(i, j+1)
        rem = 1 + solve(i+1, j)
        if solve(i, j) == replace:
            replaceChar(i+delta+1, t[j])
            backtrack(i+1, j+1)
        elif solve(i, j) == add:
            insertChar(i+delta+1, t[j])
            delta += 1
            backtrack(i, j+1)
        elif solve(i, j) == rem:
            deleteChar(i+delta+1)
            delta -= 1
            backtrack(i+1, j)

print(solve(0, 0))
backtrack(0, 0)
