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.
s,t="$"+input(),"$"+input()
n,m=len(s)-1,len(t)-1
ar=[[0]*(m+1) for i in range(n+1)]
for i in range(1,n+1):ar[i][0]=i
for j in range(1,m+1):ar[0][j]=i
for i in range(1,n+1):
    for j in range(1,m+1):
        if(s[i]==t[j]):ar[i][j]=ar[i-1][j-1]
        else:ar[i][j]=min(ar[i-1][j],ar[i-1][j-1],ar[i][j-1])+1
print(ar[n][m])
x,y=n,m
while(x+y):
    if(s[x]==t[y]):
        x-=1
        y-=1
    elif(x and y and ar[x-1][y-1]+1==ar[x][y]):
        print("REPLACE",y,t[y])
        x-=1
        y-=1
    elif(x and ar[x-1][y]+1==ar[x][y]):
        print("DELETE",x)
        x-=1
    else:
        print("INSERT",y,t[y])
        y-=1
