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

  for i in range(1, sl + 1):
      for j in range(1, tl + 1):
          if s[i - 1] == t[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
              
  return dp[-1][-1]
def trace(s, t):
  n = len(s)
  m = len(t)
  while n > 0 and m > 0:
    if s[n - 1] == t[m - 1]:
      n -= 1
      m -= 1
    else:        
      if dp[n - 1][m - 1] == dp[n][m] - 1:
        print('REPLACE', n, t[m - 1])
        n -= 1
        m -= 1
      elif dp[n - 1][m] == dp[n][m] - 1:
        print('DELETE', n)
        n -= 1
      else:
        print('INSERT', n + 1, t[m - 1])
        m -= 1
  while m > 0:
        print('INSERT', 1, t[m - 1])
        m -= 1
  while n > 0:
        print('DELETE', n)
        n -= 1
def solve():
  s = input()
  t = input()  
  global dp      
  dp = [[0]*(len(t) + 1) for _ in range(len(s) + 1)]
  print(editDistance(s, t))
  trace(s, t)

if __name__ == '__main__':
  solve()

