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.
from collections import defaultdict, Counter
from math import inf
from functools import lru_cache
from heapq import heappop, heappush

import sys
#input=sys.stdin.readline

# n = int(input())
# arr = list(map(int, input().split()))
# n,m = map(int, input().split())
def solution(): 
    a = input()
    b = input()
    
    memo = [[-1]*(len(b) + 1) for _ in range(len(a) + 1)]
    def dp(i,j):
        if i >= len(a) or j >= len(b):
            memo[i][j] = len(b) - i + len(a) - j
            return memo[i][j]

        if memo[i][j] != -1:
            return memo[i][j]

        if a[i] == b[j]:
            memo[i][j] = dp(i+1, j+1)
            return memo[i][j]
        
        delete = dp(i+1, j)
        # replace
        replace = dp(i+1, j+1)
        # add
        add = dp(i, j+1)

        memo[i][j] = min(delete, replace, add) + 1
        return memo[i][j]
     
    print(dp(0,0))

    # start from 0 0 and go on dude


    i = 0
    j = 0
    offset = 1
    while i < len(a) and j < len(b):
        if a[i] == b[j]:
            i += 1
            j += 1
            continue

        delete = memo[i+1][j] # if both out of range its zero
        replace = memo[i+1][j+1]
        add = memo[i][j+1]

        if  memo[i][j] == delete + 1:
            print("DELETE", offset + i)
            offset -= 1
            i += 1

        elif add + 1 == memo[i][j]:
            print("INSERT", offset + i, b[j])
            offset += 1
            j += 1

        elif replace + 1 == memo[i][j]:
            print("REPLACE", offset + i, b[j])
            i += 1
            j += 1

def main():
    t = 1
    #t = int(input())
    for _ in range(t):
        solution()


import sys
import threading
sys.setrecursionlimit(10**6)
threading.stack_size(1 << 27)
thread = threading.Thread(target=main)
thread.start(); thread.join()
#main()

