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 functools import lru_cache
import sys, threading

input = lambda: sys.stdin.readline().strip()

def main():

    s = input()
    t = input()

    n = len(s)
    m = len(t)

    nxt = {}

    @lru_cache(None)
    def dp(i, j):
        
        if j == m:
            return n - i
        
        if i == n:
            return m - j
        
        if s[i] == t[j]:
            nxt[i, j] = i + 1, j + 1
            return dp(i + 1, j + 1)
        else:
            add = 1 + dp(i, j + 1)
            remove = 1 + dp(i + 1, j)
            replace = 1 + dp(i + 1, j + 1)

            mn = min(add, remove, replace)

            if add == mn:
                nxt[i, j] = i, j + 1
            elif remove == mn:
                nxt[i, j] = i + 1, j 
            else:
                nxt[i, j] = i + 1, j + 1

            return mn 

    k = dp(0, 0)

    print(k)

    i = j = 0
    ri = 1

    while j < m or i < n:
        if i == n:
            print("INSERT", ri, t[j])
            j += 1
            ri += 1
        elif j == m:
            print("REMOVE", ri, s[i])
            i += 1
        else:
            if s[i] == t[j]:
                i += 1
                j += 1
                ri += 1
            else:
                if nxt[i, j] == (i, j + 1): # add char at ri
                    print("INSERT", ri, t[j])
                    j += 1
                    ri += 1
                elif nxt[i, j] == (i + 1, j):
                    print("REMOVE", ri, s[i])
                    i += 1
                    # ri -= 1
                else:
                    print("REPLACE", ri, t[j])
                    i += 1
                    j += 1
                    ri += 1

if __name__ == '__main__':
    
    sys.setrecursionlimit(1 << 30)
    threading.stack_size(1 << 27)

    main_thread = threading.Thread(target=main)
    main_thread.start()
    main_thread.join()

