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.
from functools import lru_cache
from cmath import inf
from itertools import accumulate
import sys
import threading
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    s = input()
    return(list(s[:len(s) - 1]))
def invr():
    return(map(int,input().split()))
def solve(word1,word2):
        memo = {}
        def dp(i,j):
            if (i,j) in memo:
                return memo[(i,j)]
            if i == len(word1):
                memo[(i,j)] =  len(word2) - j
            elif j == len(word2):
                memo[(i,j)] =  len(word1) - i
            elif word1[i] == word2[j]:
                memo[(i,j)] =  dp(i + 1, j + 1)
            else:
                memo[(i,j)] = 1 + min(dp(i + 1, j),dp(i, j + 1),dp(i + 1, j + 1))
            return memo[(i,j)]
        def inBound(i,j):
            return i < len(word1) and j < len(word2)
        print(dp(0,0))
        ans = []
        i,j = 0,0
        while i < len(word1) and j < len(word2):
            if word1[i] == word2[j]:
                i += 1
                j += 1
                continue
            # Make a choice
            # 0 - Replace , 1 - Insert, 2 - delete
            lowest = []
            if (i + 1,j + 1) in memo:
                lowest.append((memo[(i + 1,j + 1)],0))
            if (i + 1,j) in memo:
                lowest.append((memo[(i + 1,j)],1))
            if (i,j + 1) in memo:
                lowest.append((memo[(i,j + 1)],2))
            if not lowest:
                i += 1
                j += 1
                continue
            move = min((lowest))
            val,TYPE = move
            if TYPE == 0:
                ans.append(f"REPLACE {i} {word2[j]}")
                i += 1
                j += 1
            if TYPE == 1:
                ans.append(f"INSERT {i} {word2[j]}")
                i += 1
            if TYPE == 2:
                ans.append(f"DELETE {i} {word2[j]}")
                j += 1      
        while j < len(word2):
            ans.append(f"INSERT {i} {word2[j]}")
            i += 1
            j += 1
        
        print(*ans,sep="\n")
def main():
    solve(input(),input())
threading.stack_size(1 << 27)
sys.setrecursionlimit(1 << 30)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()