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.
#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; i++) 

string s, t;
int n, m;
int DP[1010][1010];

int dp(int i, int j)
{
    if (i == n or j == m) return DP[i][j] = n - i + m - j;

    if (DP[i][j] != -1) return DP[i][j];

    int ans = dp(i + 1, j + 1) + 1;            // replace
    if (i < n and j < m and s[i] == t[j]) ans = dp(i + 1, j + 1);  // advance
    ans = min(ans, dp(i, j + 1) + 1);          // insert
    ans = min(ans, dp(i + 1, j) + 1);          // erase

    return DP[i][j] = ans;
}

void print(int i, int j, int d)
{
    if (i == n and j == m) return;
    if (DP[i][j] == 0) return;

    if (s[i] == t[j] and DP[i][j] == DP[i + 1][j + 1]) print(i + 1, j + 1, d);
    else if (DP[i][j] == DP[i + 1][j + 1] + 1)
    {
        cout << "REPLACE " << i + d + 1 << ' ' << t[j] << '\n';
        print(i + 1, j + 1, d);
    }
    else if (DP[i][j] == DP[i][j + 1] + 1)
    {
        cout << "INSERT " << i + d + 1 << ' ' << t[j] << '\n';
        print(i, j + 1, d + 1);
    }
    else if (DP[i][j] == DP[i + 1][j] + 1)
    {
        cout << "DELETE " << i + d + 1 << '\n';
        print(i + 1, j, d - 1);
    }
}

int main()
{
    cin >> s >> t;
    n = s.size(), m = t.size();

    memset(DP, -1, sizeof DP);
    
    cout << dp(0, 0) << '\n';
    print(0, 0, 0);
}