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
import threading
from functools import lru_cache
s = list(input())
t = list(input())


def main():
    @lru_cache(None)
    def dp(i, j):
        if i == len(s):
            if j == len(t):
                return [0, []]
            return [len(t) - j, ["INSERT"]]
        if j == len(t):
            if i == len(s):
                return [0, []]
            return [len(s) - i,  ["DELETE"]]

        if s[i] == t[j]:
            return dp(i+1, j+1)
        else:
            ans = [float('inf'), []]
            val = dp(i+1, j)
            if val[0] < ans[0]:
                new_arr = ['DELETE ' + str(i+1)]
                new_arr.extend(val[1])
                ans = [val[0] + 1,  new_arr]
            val = dp(i, j+1)
            if val[0] < ans[0]:
                new_arr = ['INSERT ' + str(j+1) + " " + t[j]]
                new_arr.extend(val[1])
                ans = [val[0] + 1,  new_arr]
            val = dp(i+1, j+1)
            if val[0] < ans[0]:
                new_arr = ["REPLACE " + str(j+1) + " " + t[j]]
                new_arr.extend(val[1])
                ans = [val[0] + 1, new_arr]

            return ans

    ans = dp(0, 0)
    print(ans[0])
    for i in range(ans[0]):
        if ans[1][i] == "DELETE" or ans[1][i] == "INSERT":
            continue
        print(ans[1][i])

    if ans[1][-1] == "INSERT":
        j = len(t) - 1

        while s[-1] != t[j]:
            print("INSERT " + str(j+1) + " " + t[i])
            j -= 1

    if ans[1][-1] == "DELETE":
        j = len(t) - 1
        while s[-1] != t[j]:
            print("DELETE " + str(j+1))
            j -= 1


threading.stack_size(1 << 27)
sys.setrecursionlimit(1 << 30)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()
