import sys

COST_DEL = 1
COST_INS = 1
COST_SUBST = 1
COST_MATCH = 0

COST = []
OP = []

def solve(s,t):
  global COST, OP
  sl = len(s)
  tl = len(t)
  COST = [[0 for i in range(tl+1)] for j in range(sl+1)]
  OP = [['' for i in range(tl+1)] for j in range(sl+1)]
  COST[0][0] = 0
  for i in range(1,sl+1):
    COST[i][0] = COST[i-1][0] + COST_DEL
    OP[i][0] += 'D'
  for i in range(1,tl+1):
    COST[0][i] = COST[0][i-1] + COST_INS
    OP[0][i] += 'I'
  for i in range(1,sl+1):
    for j in range(1,tl+1):
      c_d = COST[i][j-1] + COST_DEL
      c_i = COST[i-1][j] + COST_INS
      c_s = COST[i-1][j-1] + COST_SUBST
      if s[i-1]==t[j-1]: c_m = COST[i-1][j-1] + COST_MATCH
      else: c_m = sys.maxsize
      COST[i][j] = min(c_d, c_i, c_s, c_m)
      if (c_d == COST[i][j]): OP[i][j] += 'D'
      if (c_i == COST[i][j]): OP[i][j] += 'I'
      if (c_s == COST[i][j]): OP[i][j] += 'S'
      if (c_m == COST[i][j]): OP[i][j] += 'M'
  return COST[sl][tl], getPath(s,t)

def getPath(s,t):
  global OP
  r = []
  row = len(s)
  col = len(t)
  while row > 0 or col > 0:
    s_ch = s[row-1]
    t_ch = t[col-1]
    if  'M' in OP[row][col]:
      r.append('MATCH '+s_ch)
      row -= 1
      col -= 1
    elif 'S' in OP[row][col]:
      r.append('SUBSTITUTE '+s_ch+' with '+t_ch)
      row -= 1
      col -= 1
    elif 'I' in OP[row][col]:
      r.append('INSERT '+t_ch)
      col -= 1
    elif 'D' in OP[row][col]:
      r.append('DELETE '+s_ch)
      row -= 1
  r.reverse()
  return r