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.
class Solution:
    def __init__(self, s, t):
        self.s = s
        self.t = t
        self.m = len(s)
        self.n = len(t)
        self.dp = [[0] * (self.n + 1) for _ in range(self.m + 1)]

    def dfs(self, i, j):
        if i == 0 and j == 0:
            return
        if i >= 1 and self.dp[i][j] == self.dp[i-1][j]+1:
            self.dfs(i-1, j)
            print(f'DELETE {j+1}')
        elif j >= 1 and self.dp[i][j] == self.dp[i][j-1]+1:
            self.dfs(i, j-1)
            print(f'INSERT {j} {self.t[j-1]}')
        else:
            self.dfs(i-1, j-1)
            if self.s[i-1] != self.t[j-1]:
                print(f'REPLACE {j} {self.t[j-1]}')

    def dynamo(self):
        for i in range(self.m + 1):
            self.dp[i][0] = i
        for j in range(self.n + 1):
            self.dp[0][j] = j

        for i in range(1, self.m+1):
            for j in range(1, self.n+1):
                if self.s[i-1] == self.t[j-1]:
                    self.dp[i][j] = self.dp[i-1][j-1]
                else:
                    self.dp[i][j] = 1+min(self.dp[i][j-1], self.dp[i-1][j], self.dp[i-1][j-1])
        print(self.dp[-1][-1])
        self.dfs(self.m, self.n)


def main():
    s = input()
    t = input()
    sol = Solution(s, t)
    sol.dynamo()
    

if __name__ == "__main__":
    main()

          			  				  	 		  	 	