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.
def answer(first, second):
    dp = [[0 for _ in range(len(first)+1)] for _ in range(len(second)+1)]

    for i in range(len(first)-1, -1, -1):
        dp[-1][i] = dp[-1][i+1] + 1

    for i in range(len(second)-1, -1, -1):
        dp[i][-1] = dp[i+1][-1] + 1

    for i in range(len(second)-1, -1, -1):
        for j in range(len(first)-1, -1, -1):
            if first[j] == second[i]:
                dp[i][j] = dp[i+1][j+1]
            else:
                dp[i][j] = min(dp[i+1][j], dp[i][j+1], dp[i+1][j+1]) + 1


    print(dp[0][0])
    start, end = 0, 0
    result = []
    while (start, end) != (len(second), len(first)):
        if start < len(second) and end < len(first):
            newmin = min(dp[start+1][end+1], dp[start+1][end], dp[start][end+1])
            if newmin != dp[start][end]:
                if dp[start+1][end+1] <= dp[start+1][end] and dp[start+1][end+1] <= dp[start][end+1]:
                    print("REPLACE " + str(start+1) + " " + second[start])
                    start, end = start+1, end+1
                elif dp[start+1][end] <= dp[start+1][end+1] and dp[start+1][end] <= dp[start][end+1]:
                    print("INSERT " + str(start+1) + " " + second[start])
                    start, end = start+1, end
                else:
                    print("DELETE " + str(start+1))
                    start, end = start, end+1
            else: 
                start, end = start+1, end+1
    
first = input()
second = input()
answer(first, second)