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 = input()
t = input()
sl, tl = len(s), len(t)
dp = [[0]*(tl + 1) for _ in range(sl + 1)]
for i in range(tl + 1):
  dp[0][i] = i
for i in range(sl + 1):
  dp[i][0] = i
dp[0][0] = 0

for i in range(sl):
    dp[i][-1] = sl - i
for j in range(tl):
    dp[-1][j] = tl - j
dp[-1][-1] = 0        
for i in range(sl - 1, -1, -1):
    for j in range(tl - 1, -1, -1):
        if s[i] == t[j]:
            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])
# print(dp)

i, j = 0, 0
while i < sl and j < tl:
  if s[i] == t[j]:
    i += 1
    j += 1
  else:
    ins = dp[i][j + 1]
    dele = dp[i + 1][j]
    rep = dp[i + 1][j + 1] 
    act = min(ins, dele, rep)   
    if act == ins:
      print('INSERT', i + 1, t[j - 1])
      j += 1
    elif act == rep:
      print('REPLACE', i + 1, t[j - 1])
      i += 1
      j += 1
    else:
      print('DELETE', i + 1 )
      i += 1
while i < sl:
      print('DELETE', i + 1)
      i += 1 
while j < tl:
      print('INSERT', i + 1, t[j - 1])
      j += 1   