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 main():
    s = input()
    t = input()
    m = len(s)
    n = len(t)
    dp = [[0] * (n+1) for _ in range(m+1)]
    ops = [['F'] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    for i in range(1, m+1):
        for j in range(1, n+1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1]
                ops[i][j] = 'M'
            else:
                dp[i][j] = 1+min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1])
                if dp[i][j] == 1+dp[i-1][j-1]:
                    ops[i][j] = 'R'
                elif dp[i][j] == 1+dp[i-1][j]:
                    ops[i][j] = 'D'
                elif dp[i][j] == 1+dp[i][j-1]:
                    ops[i][j] = 'I'
    print(dp[-1][-1])
    sol = []
    i = m
    j = n
    while i > 0 and j > 0:
        tag = max(i, j)
        if ops[i][j] == 'R':
            sol.append(f'Replace {tag} {t[j-1]}')
            i -= 1
            j -= 1
        elif ops[i][j] == 'D':
            sol.append(f'Delete {tag}')
            i -= 1
        elif ops[i][j] == 'I':
            sol.append(f'Insert {tag+1} {t[j-1]}')
            j -= 1
        else:
            i -= 1
            j -= 1


    while i > 0:
        sol.append(f'Delete {i}')
        i -= 1
    while j > 0:
        sol.append(f'Insert {j} {t[j - 1]}')
        j -= 1

    for i in range(len(sol)-1, -1, -1):
        print(sol[i])


if __name__ == "__main__":
    main()

 			  				 	 	   	 	    		  	