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.

import sys
from collections import defaultdict

readline = sys.stdin.readline

def read_input() -> tuple:
    source = readline().strip()
    target = readline().strip()
    return source, target

def solve():
    source, target = read_input()
    n, m = len(source), len(target)
    dp = [[n + m + 1] * (m + 1) for _ in range(n + 1)]
    dp[0][0] = 0
    guide = defaultdict(list)

    for i in range(n + 1):
        if i > 0:
            dp[i][0] = dp[i - 1][0] + 1
            guide[i, 0] = [i - 1, 0]
        for j in range(m + 1):
            if j > 0 and dp[i][j] > dp[i][j - 1] + 1: # means insert, t[j -1] in s[ - 1]
                dp[i][j] = dp[i][j - 1] + 1
                guide[i, j] = [i, j - 1]
            if i > 0 and dp[i][j] > dp[i - 1][j] + 1: # means delete [i]
                dp[i][j] = dp[i - 1][j] + 1
                guide[i, j] = [i- 1, j]
            if i > 0 and j > 0:
                if dp[i][j] > dp[i - 1][j - 1] + int(source[i - 1] != target[j - 1]):
                    dp[i][j] = dp[i - 1][j - 1] + int(source[i - 1] != target[j - 1]) # replace or skip
                    guide[i, j] = [i - 1, j -1]
    print(dp[-1][-1])
    
    ops = []
    i, j = n, m
    while i != 0 or j != 0:
        i1, j1 = guide[i, j]
        if i1 == i - 1 and j1 == j - 1:
            if source[i- 1] != target[j - 1]:
                ops.append('REPLACE '+str(i) +' ' +target[j -1])
        elif i1 == i - 1:
            ops.append('DELETE '+str(i1))
        else:
            ops.append('INSERT '+str(i1 + 1) + ' ' + target[j1])
        i, j = i1, j1

    for op in ops[::-1]:
        print(op)


def write_output():
    pass

solve()