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 edit_distance(S, T):
    '''
    modify S to T
    :param S:
    :param T:
    :return:
    '''
    for i in range(len(T) + 1):
        f[0][i] = i
    for i in range(len(S) + 1):
        f[i][0] = i
    for i in range(1, len(S) + 1):
        for j in range(1, len(T) + 1):
            if S[i - 1] == T[j - 1]:
                f[i][j] = f[i - 1][j - 1]
            else:
                f[i][j] = min(f[i - 1][j - 1], f[i - 1][j], f[i][j - 1]) + 1
    return f[len(S)][len(T)]


def trace(S, T):
    transform = []
    n = len(S)
    m = len(T)
    while n > 0 and m > 0:
        if S[n - 1] == T[m - 1]:
            n -= 1
            m -= 1
        elif f[n - 1][m - 1] == (f[n][m] - 1):
            print('REPLACE {} {}'.format(n, T[m-1]))
            n -= 1
            m -= 1
        elif f[n - 1][m] == (f[n][m] - 1):
            print('DELETE {} {}'.format(n, S[n-1]))
            n -= 1
        else:
            print('INSERT {} {}'.format(n+1, T[m-1]))
            m -= 1
    while m > 0:
        print('INSERT {} {}'.format(1, T[m-1]))
        m -= 1
    while n > 0:
        print('DELETE {} {}'.format(n, S[n-1]))
        n -= 1
    return ''.join(transform)


def solve():
    # ABA
    # ABBBA
    S = input()
    T = input()
    global f
    f = [[0] * (len(T) + 1) for _ in range(len(S) + 1)]
    print(edit_distance(S, T))
    print(trace(S, T))


if __name__ == '__main__':
    solve()
