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 collections

# abcdef
# azced

def main():
    source = input()
    destination = input()
    n = len(source)
    m = len(destination)
    res = []

    dp = [[0 for i in range(n+1)] for i in range(m+1)]

    for i in range(len(dp[0])):
        dp[0][i] = i

    for i in range(len(dp)):
        dp[i][0] = i

    for i in range(1,m+1):
        for j in range(1,n+1):
            if destination[i-1] == source[j-1]:
                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

    i = m
    j = n
    while i > 0 and j > 0:
        val = dp[i][j] - 1
        if destination[i-1] == source[j-1]:
            i -= 1
            j -= 1
        else:
            if dp[i-1][j] == val:
                res.append('INSERT ' + str(i)  + ' ' + destination[i-1])
                i -= 1
            elif dp[i][j-1] == val:
                j -= 1
                res.append('D')
            else:
                res.append('REPLACE ' + str(i)  + ' ' + destination[i-1])
                i -= 1
                j -= 1

    for i in res[::-1]:
        print(i)





main()
 			 	  		 				 	    				  		 	