#include<bits/stdc++.h>
using namespace std ;
typedef long long ll ;
typedef unsigned long long ull ;
typedef pair < int , int > pii ;
typedef vector < int > vi ;
#define fi first
#define se second
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int MAXN = 1e6 + 7 ;
const int MAXK = 1007 ;

int n , m , k ;
string a , b ;
pii dp[ MAXK ][ 2 * MAXK ] , prv[ MAXK ][ 2 * MAXK ] ;

ll MOD[ 2 ] = { 1e9 + 7 , 998244353 } ;
ll pw[ 2 ][ MAXN ] ;
ll base = 26 ;

struct hsh {
    ll val[ 2 ] ;
    hsh ( ) { val[ 0 ] = val[ 1 ] = 0 ; }
};

void init ( ) {
    pw[ 0 ][ 0 ] = pw[ 1 ][ 0 ] = 1 ;
    for ( int i = 1 ; i < MAXN ; ++ i ) {
        pw[ 0 ][ i ] = ( pw[ 0 ][ i - 1 ] * base ) % MOD[ 0 ] ;
        pw[ 1 ][ i ] = ( pw[ 1 ][ i - 1 ] * base ) % MOD[ 1 ] ;
    }
}

hsh pref[ 2 ][ MAXN ] ;

hsh get_hash ( int l , int r , int id ) {
    if ( l > r ) { return hsh ( ) ; }
    hsh ret = pref[ id ][ r ] ;
    hsh aux = pref[ id ][ l - 1 ] ;
    aux.val[ 0 ] = ( aux.val[ 0 ] * pw[ 0 ][ r - l + 1 ] ) % MOD[ 0 ] ;
    aux.val[ 1 ] = ( aux.val[ 1 ] * pw[ 1 ][ r - l + 1 ] ) % MOD[ 1 ] ;
    ret.val[ 0 ] = ( ret.val[ 0 ] + MOD[ 0 ] - aux.val[ 0 ] ) % MOD[ 0 ] ;
    ret.val[ 1 ] = ( ret.val[ 1 ] + MOD[ 1 ] - aux.val[ 1 ] ) % MOD[ 1 ] ;
    return ret ;
}

pii extend ( int x , int y ) {
    int l , r , mid ;
    l = 0 , r = min ( n - x , m - y ) ;
    while ( l < r ) {
        mid = ( l + r + 1 ) / 2 ;
        hsh aux1 = get_hash ( x + 1 , x + mid , 0 ) ;
        hsh aux2 = get_hash ( y + 1 , y + mid , 1 ) ;
        if ( aux1.val[ 0 ] == aux2.val[ 0 ] && aux1.val[ 1 ] == aux2.val[ 1 ] ) { l = mid ; }
        else { r = mid - 1 ; }
    }
    return { x + l , y + l } ;
}

void solve ( ) {
    cin >> n >> m >> k ;
    cin >> a >> b ;
    for ( int i = 1 ; i <= n ; ++ i ) {
        pref[ 0 ][ i ] = pref[ 0 ][ i - 1 ] ;
        pref[ 0 ][ i ].val[ 0 ] = ( base * pref[ 0 ][ i ].val[ 0 ] + ( a[ i - 1 ] - 'a' ) ) % MOD[ 0 ] ;
        pref[ 0 ][ i ].val[ 1 ] = ( base * pref[ 0 ][ i ].val[ 1 ] + ( a[ i - 1 ] - 'a' ) ) % MOD[ 1 ] ;
    }
    for ( int i = 1 ; i <= m ; ++ i ) {
        pref[ 1 ][ i ] = pref[ 1 ][ i - 1 ] ;
        pref[ 1 ][ i ].val[ 0 ] = ( base * pref[ 1 ][ i ].val[ 0 ] + ( b[ i - 1 ] - 'a' ) ) % MOD[ 0 ] ;
        pref[ 1 ][ i ].val[ 1 ] = ( base * pref[ 1 ][ i ].val[ 1 ] + ( b[ i - 1 ] - 'a' ) ) % MOD[ 1 ] ;
    }
    for ( int i = 0 ; i <= k + 1 ; ++ i ) {
        for ( int j = MAXK - k ; j <= MAXK + k ; ++ j ) {
            dp[ i ][ j ] = { -1 , -1 } ;
        }
    }
    dp[ 0 ][ MAXK ] = extend ( 0 , 0 ) ;
    for ( int lvl = 0 ; lvl < k ; ++ lvl ) {
        for ( int diff = -k ; diff <= k ; ++ diff ) {
            if ( dp[ lvl ][ diff + MAXK ].fi == -1 ) { continue ; }
            auto [ x , y ] = dp[ lvl ][ diff + MAXK ] ;
            {
                if ( x + 1 <= n ) { 
                    auto [ nx , ny ] = extend ( x + 1 , y ) ;
                    if ( dp[ lvl + 1 ][ diff + MAXK + 1 ] < make_pair ( nx , ny ) ) {
                        dp[ lvl + 1 ][ diff + MAXK + 1 ] = { nx , ny } ;
                        prv[ lvl + 1 ][ diff + MAXK + 1 ] = { -1 , x + 1 } ;
                    }
                }
            }
            {
                if ( y + 1 <= m ) {
                    auto [ nx , ny ] = extend ( x , y + 1 ) ;
                    if ( dp[ lvl + 1 ][ diff + MAXK - 1 ] < make_pair ( nx , ny ) ) {
                        dp[ lvl + 1 ][ diff + MAXK - 1 ] = { nx , ny } ;
                        prv[ lvl + 1 ][ diff + MAXK - 1 ] = { 1 , x + 1 } ;
                    }
                }
            }
            {
                if ( x + 1 <= n && y + 1 <= m ) {
                    auto [ nx , ny ] = extend ( x + 1 , y + 1 ) ;
                    if ( dp[ lvl + 1 ][ diff + MAXK ] < make_pair ( nx , ny ) ) {
                        dp[ lvl + 1 ][ diff + MAXK ] = { nx , ny } ;
                        prv[ lvl + 1 ][ diff + MAXK  ] = { 0 , x + 1 } ;
                    }
                }
            }
        }
    }
    int act = n - m ;
    for ( int i = 0 ; i <= k ; ++ i ) {
        if ( dp[ i ][ act + MAXK ].fi == n ) {
            cout << "YES\n" ;
            vector < pair < pii , char > > ans ;
            int x = n , y = m , hh = i ;
            while ( x > 0 || y > 0 ) {
                if ( x > 0 && y > 0 && a[ x - 1 ] == b[ y - 1 ] ) {
                    -- x , -- y ;
                    continue ;
                }
                if ( prv[ hh ][ x - y + MAXK ].fi == -1 ) {
                    ans.push_back ( { prv[ hh ][ x - y + MAXK ] , 'a' } ) ;
                    -- x ;
                }
                else if ( prv[ hh ][ x - y + MAXK ].fi == 0 ) {
                    ans.push_back ( { prv[ hh ][ x - y + MAXK ] , b[ y - 1 ] } ) ;
                    -- x , -- y ;
                }
                else {
                    ans.push_back ( { prv[ hh ][ x - y + MAXK ] , b[ y - 1 ] } ) ;
                    -- y ;
                }
                -- hh ;
            }
            cout << (int)ans.size ( ) << "\n" ;
            for ( auto [ wh , c ] : ans ) {
                if ( wh.fi == -1 ) {
                    cout << "DELETE " << wh.se << "\n" ;
                }
                else if ( wh.fi == 0 ) {
                    cout << "REPLACE " << wh.se << " " << c << "\n" ;
                }
                else {
                    cout << "INSERT " << wh.se << " " << c << "\n" ;
                }
            }
            return ;
        }
    }
    cout << "NO\n" ;
}


int main ( ) {
    ios_base :: sync_with_stdio ( false ) ;
    cin.tie ( NULL ) ;
    init ( ) ;
    int t = 1 ; cin >> t ;
    while ( t -- ) { solve ( ) ; }
    return 0 ;
}

answer.code:18:37: error: narrowing conversion of ‘1.000000007e+9’ from ‘double’ to ‘ll’ {aka ‘long long int’} [-Wnarrowing]
   18 | ll MOD[ 2 ] = { 1e9 + 7 , 998244353 } ;
      |                                     ^