//#define TESTING

#pragma GCC optimize ("-O3")
#pragma optimize("t", on)

#ifdef _WIN32
#  define LL "%I64d"
#else
#  define LL "%Ld"
#endif

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <ctime>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <bitset>
#include <string>
#include <algorithm>
#include <complex>
#include <utility>
#include <cassert>
using namespace std;
#define null NULL
#define mp make_pair
#define pb(a) push_back(a)
#define sz(a) ((int)(a).size())
#define all(a) a.begin() , a.end()
#define fi first
#define se second
#define relaxMin(a , b) (a) = min((a),(b))
#define relaxMax(a , b) (a) = max((a),(b))
#define SQR(a) ((a)*(a))
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
#define MAX_L 200010
#define MAX_WRD_L 110
#define MAX_WRD_C 55
int big_rand(){
  return (rand()<<10) ^ rand();
}

// Optimize
typedef pair<int , pii> state;
typedef pair< int , pair<pii , int> > cut_state;
int main()
__attribute__((optimize("-O3")));
void read()
__attribute__((optimize("-O3")));
//void write()
//__attribute__((optimize("-O2")));
int score()
__attribute__((optimize("-O3")));
state one_center(int)
__attribute__((optimize("-O3")));
state two_centers(int , int)
__attribute__((optimize("-O3")));
state put_word(int)
__attribute__((optimize("-O3")));
int configure()
__attribute__((optimize("-O3")));
void generate(int)
__attribute__((optimize("-O3")));
void best_move()
__attribute__((optimize("-O3")));
state straight(int)
__attribute__((optimize("-O3")));
state straight_move(int , int)
__attribute__((optimize("-O3")));
void solve()
__attribute__((optimize("-O3")));
int apply_cut(int , int , int)
__attribute__((optimize("-O3")));
cut_state best_cut()
__attribute__((optimize("-O3")));
cut_state best_with_profile(int , int)
__attribute__((optimize("-O3")));
cut_state best_profile()
__attribute__((optimize("-O3")));
// </end>

// Input
FILE* rfile = /*stdin;*/ fopen("fixdna.in" , "r");
FILE* wfile = /*stdout;*/ fopen("fixdna.out" , "w");
int N , K , T;
char SRC[MAX_L] , SNK[MAX_L];
int PR[32][32] , *PR_P[MAX_L];
int WRDC , WRDL[MAX_WRD_C];
char WRD[MAX_WRD_C][MAX_WRD_L];
void read(){
  #ifndef TESTING
  fscanf(rfile , "%d%d%d" , &N , &K , &T);
  fscanf(rfile , "%s" , &SRC);
  fscanf(rfile , "%s" , &SNK);
  for(int i=0;i<K;++i)
   for(int j=0;j<K;++j)
    fscanf(rfile , "%d" , &PR[i][j]);
  fscanf(rfile , "%d" , &WRDC);
  for(int i=0;i<WRDC;++i)
   fscanf(rfile , "%s" , &WRD[i]),
   WRDL[i] = strlen(WRD[i]);
  #else
  N = 20000 , K = 15 , T = 1000;
  for(int i=0;i<N;++i)
   SRC[i] = rand()%K + 'a';
  for(int i=0;i<N;++i)
   SNK[i] += rand()%K + 'a';
  for(int i=0;i<K;++i)
   for(int j=0;j<K;++j)
    PR[i][j] = (i == j) ? 0 : rand()%40 + 1;
  for(int i=0;i<K;++i)
   for(int j=i+1;j<K;++j)
    PR[j][i] = PR[i][j];
  WRDC = 25;
  for(int i=0;i<WRDC;++i){
   WRDL[i] = rand()%50 + 1;
   for(int j=0;j<WRDL[i];++j)
    WRD[i][j] += rand()%K + 'a';
                         }
  #endif
  for(int i=0;i<N;++i)
   SRC[i] -= 'a',
   SNK[i] -= 'a',
   PR_P[i] = PR[SNK[i]];
  for(int i=0;i<WRDC;++i)
   for(int j=0;j<WRDL[i];++j)
    WRD[i][j] -= 'a';
}
// Output
vector< pair<int , pii> > out;
vi add_info;
void write(){
  fprintf(wfile , "%d\n" , sz(out));
  for(int i=0;i<sz(out);++i)
   if(out[i].fi != 1)
    fprintf(wfile , "%d %d %d\n" , out[i].fi,
            out[i].se.fi , out[i].se.se);
   else
    fprintf(wfile , "%d %d %d %d\n" , out[i].fi,
            out[i].se.fi , out[i].se.se,
            add_info[i]);
  exit(0);
}
// Helpers
int score(){
  int ret = 0;
  for(int i=0;i<N;++i)
   ret += PR_P[i][SRC[i]];
  return ret;
}
int BORDER;
state one_center(int c){
  int val = 0 , f = 0 , t = 0;
  int lo = c , hi = c , dlt = 0;
  int lo_lim = max(0 , c - BORDER);
  int hi_lim = min(N , c + BORDER);
  while(--lo >= lo_lim && ++hi < hi_lim){
   dlt -= PR_P[lo][SRC[lo]],
   dlt -= PR_P[hi][SRC[hi]],
   dlt += PR_P[lo][SRC[hi]],
   dlt += PR_P[hi][SRC[lo]];
   if(dlt < val)
    val = dlt,
    f = lo , t = hi;
                                        }
  return state(val , mp(f , t));
}
state two_centers(int c1 , int c2){
  int val = 0 , f = 0 , t = 0;
  if(c2 >= N) return state(val , mp(f , t));
  int lo = c1 + 1 , hi = c2 - 1 , dlt = 0;
  int lo_lim = max(0 , c1 - BORDER);
  int hi_lim = min(N , c2 + BORDER);
  while(--lo >= lo_lim && ++hi < hi_lim){
   dlt -= PR_P[lo][SRC[lo]],
   dlt -= PR_P[hi][SRC[hi]],
   dlt += PR_P[lo][SRC[hi]],
   dlt += PR_P[hi][SRC[lo]];
   if(dlt < val)
    val = dlt,
    f = lo , t = hi;
                                        }
  return state(val , mp(f , t));
}
state put_word(int c){
  int val = 0 , f = 0 , cv;
  for(int i=0;i<WRDC;++i){
   int cl = WRDL[i];
   if(c + cl > N) continue;
   char* w = WRD[i];
   cv = 0 , cl += c;
   for(int j=c;j<cl;++j)
    cv -= PR_P[j][SRC[j]],
    cv += PR_P[j][w[j-c]];
   if(cv < val)
    val = cv,
    f = i;
                         }
  return state(val , mp(f , c));
}
int BEG_BORDER , MID_BORDER , LAST_BORDER;
int MID_LIMIT , LAST_LIMIT;
int EXPENSIVE = -1 , EBORDER = 0;
int TRY_FLIPS , TRY_WORDS;
int STR_LIM_LO , STR_LIM_HI;
int B_STR_LIM_LO , B_STR_LIM_HI , B_STR;
int PROF_UP , PROF_SPAN;
int configure(){
  if(N <= 100 && T <= 20)
    BEG_BORDER = N , MID_BORDER = 500, LAST_BORDER = 70,
    MID_LIMIT = 35 , LAST_LIMIT = 70,
    TRY_FLIPS = 1000 , TRY_WORDS = 1000,
    STR_LIM_LO = 1 , STR_LIM_HI = N,
    B_STR = T + 100,
    PROF_UP = 0 , PROF_SPAN = 0;
  else if(N <= 1000 && T <= 100)
    BEG_BORDER = N , MID_BORDER = 500, LAST_BORDER = 70,
    MID_LIMIT = 35 , LAST_LIMIT = 70,
    TRY_FLIPS = 1000 , TRY_WORDS = 1000,
    STR_LIM_LO = 1 , STR_LIM_HI = N,
    B_STR = T + 100,
    PROF_UP = 40 , PROF_SPAN = 17;
  else if(N <= 5000 && T <= 500)
    BEG_BORDER = N , MID_BORDER = 250, LAST_BORDER = 70,
    MID_LIMIT = 35 , LAST_LIMIT = 70,
    TRY_FLIPS = 1000 , TRY_WORDS = 1000,
    STR_LIM_LO = 1 , STR_LIM_HI = min(N , 200),
    B_STR = 30,
    B_STR_LIM_LO = 1 , B_STR_LIM_HI = min(N , 20),
    PROF_UP = 0 , PROF_SPAN = 0;
  else if(N <= 20000 && T <= 1000)
    BEG_BORDER = N , MID_BORDER = 200, LAST_BORDER = 60,
    MID_LIMIT = 50 , LAST_LIMIT = 150,
    TRY_FLIPS = 300 , TRY_WORDS = 150,
    STR_LIM_LO = 3 , STR_LIM_HI = 11,
    B_STR = T + 100,
    PROF_UP = 0 , PROF_SPAN = 0;
  else BEG_BORDER = 200 , MID_BORDER = 100,
       LAST_BORDER = 40,
       MID_LIMIT = 1800 , LAST_LIMIT = 6000,
       TRY_FLIPS = 140 , TRY_WORDS = 0,
       STR_LIM_LO = 1 , STR_LIM_HI = 0,
       B_STR = T + 100,
       PROF_UP = 0 , PROF_SPAN = 0;
}
int USED[MAX_L] , UST;
int cand[MAX_L] , cand_c;
state bflip , bput , bchange;
void generate(int how){
  if(4*how >= N){
   for(int i=0;i<N;++i) cand[i] = i;
   random_shuffle(cand , cand + N);
   cand_c = how;
                }
  else{
   ++UST , cand_c = 0;
   for(int i=0;i<(how<<1);++i){
    cand[cand_c] = big_rand() % N;
    if(USED[cand[cand_c]] == UST)
     continue;
    if(++cand_c >= how) break;
                              }
      }
}
void best_move(){
  bflip = bput = state(0 , mp(0,0));
  int how = min(TRY_FLIPS , N);
  generate(how);
  for(int i=0;i<cand_c;++i)
   relaxMin(bflip , one_center(cand[i])),
   relaxMin(bflip , two_centers(cand[i],
                                cand[i] + 1));
  how = min(TRY_WORDS , N);
  generate(how);
  for(int i=0;i<cand_c;++i)
   relaxMin(bput , put_word(cand[i]));
}
state straight(int len){
  int l1 = 0 , r1 = len - 1;
  int l2 = len , r2 = 2*len - 1;
  if(r2 >= N) return state(0 , mp(0,0));
  int bst = 0 , dlt = 0;
  int bf = 0 , bt = 0;
  for(int i=0;i<len;++i)
   dlt -= PR_P[l1+i][SRC[l1+i]] +
          PR_P[l2+i][SRC[l2+i]],
   dlt += PR_P[l1+i][SRC[l2+i]] +
          PR_P[l2+i][SRC[l1+i]];
  if(dlt < bst)
   bst = dlt,
   bf = l1 , bt = l2;
  while(r2+1 < N){
   dlt += PR_P[l1][SRC[l1]];
   dlt += PR_P[l2][SRC[l2]];
   dlt -= PR_P[l1][SRC[l2]];
   dlt -= PR_P[l2][SRC[l1]];
   ++l1 , ++l2;
   ++r1 , ++r2;
   dlt -= PR_P[r1][SRC[r1]];
   dlt -= PR_P[r2][SRC[r2]];
   dlt += PR_P[r1][SRC[r2]];
   dlt += PR_P[r2][SRC[r1]];
   if(dlt < bst)
    bst = dlt,
    bf = l1 , bt = l2;
                 }
  return state(bst , mp(bf,bt));
}
state straight_move(int lo , int hi){
  state val(0 , mp(0,0));
  for(int i=lo;i<=hi;++i)
   relaxMin(val , straight(i));
  return val;
}
// Only for group 2
char BUF[MAX_L];
int apply_cut(int f , int t , int p){
  int bp = 0 , len = t - f + 1 , val = 0;
  for(int i=0;i<f;++i)
   BUF[bp++] = SRC[i];
  for(int i=t+1;i<N;++i)
   BUF[bp++] = SRC[i];
  for(int i=bp-1;i>=p;--i)
   BUF[i + len] = BUF[i];
  for(int i=0;i<len;++i)
   BUF[p + i] = SRC[f + i];
  for(int i=0;i<N;++i)
   val -= PR_P[i][SRC[i]],
   val += PR_P[i][BUF[i]];
  return val;
}
cut_state best_with_profile(int len1 , int len2){
  if(len1 <= 1 || len2 <= 1)
   return mp(0 , mp(mp(0,0) , 0));
  if(len1 == len2)
   return mp(0 , mp(mp(0,0) , 0));
  int l1 = 0 , r1 = len1 - 1;
  int l2 = len1 , r2 = len1 + len2 - 1;
  if(r2 >= N)
   return mp(0 , mp(mp(0,0) , 0));
  int bst = 0 , dlt = 0;
  int bf = 0 , bt = 0;
  for(int i=0;i<=r2;++i)
   dlt -= PR_P[l1 + i][SRC[l1 + i]];
  for(int i=0;i<len1;++i)
   dlt += PR_P[l1+i+len2][SRC[l1+i]];
  for(int i=0;i<len2;++i)
   dlt += PR_P[l2+i-len1][SRC[l2+i]];
  if(dlt < bst)
   bst = dlt,
   bf = l1 , bt = l2;
  while(r2+1 < N){
   dlt += PR_P[l1][SRC[l1]];
   dlt += PR_P[l2][SRC[l2]];
   dlt -= PR_P[l1 + len2][SRC[l1]];
   dlt -= PR_P[l2 - len1][SRC[l2]];
   ++l1 , ++l2;
   ++r1 , ++r2;
   dlt -= PR_P[r1][SRC[r1]];
   dlt -= PR_P[r2][SRC[r2]];
   dlt += PR_P[r1 + len2][SRC[r1]];
   dlt += PR_P[r2 - len1][SRC[r2]];
   if(dlt < bst)
    bst = dlt,
    bf = l1 , bt = l2;
                 }
  return mp(bst , mp(mp(bf , bt-1) , bf + len2));
}
cut_state best_profile(){
  cut_state bcut(0 , mp(mp(0,0) , 0));;
  for(int i=2;i<PROF_UP;++i)
    for(int j=i-PROF_SPAN;j<=i+PROF_SPAN;++j)
     relaxMin(bcut , best_with_profile(i , j));
  return bcut;
}
// Solution
void iterate(){
  for(int i=0;i<T;++i){
   BORDER = BEG_BORDER;
   if(i >= MID_LIMIT)
    BORDER = MID_BORDER;
   if(i >= LAST_LIMIT)
    BORDER = LAST_BORDER;
   best_move();
   int SLO = STR_LIM_LO , SHI = STR_LIM_HI;
   if(i > B_STR)
    SLO = B_STR_LIM_LO , SHI = B_STR_LIM_HI;
   bchange = straight_move(SLO , SHI);
   cut_state bcut = best_profile();
   if(bcut.fi < min(bchange.fi,
                    min(bflip.fi , bput.fi))){
    //cout<<bcut.se.fi.se - bcut.se.fi.fi<<endl;
    //cout<<bcut.se.se - bcut.se.fi.fi<<endl;
    //system("pause");
    apply_cut(bcut.se.fi.fi , bcut.se.fi.se,
              bcut.se.se);
    memcpy(SRC , BUF , N*sizeof(char));
    out.pb(mp(1 , bcut.se.fi));
    add_info.pb(bcut.se.se);
                                             }
   else if(bchange.fi < min(bflip.fi , bput.fi)){
    int wlen = bchange.se.se - bchange.se.fi;
    for(int i=0;i<wlen;++i)
     swap(SRC[bchange.se.fi + i],
          SRC[bchange.se.se + i]);
    out.pb(mp(1 , mp(bchange.se.fi ,
                     bchange.se.se-1)));
    add_info.pb(bchange.se.se);
                                                }
   else if(bput.fi < bflip.fi){
         char* w = WRD[bput.se.fi];
         int wlen = WRDL[bput.se.fi],
             p = bput.se.se;
         for(int j=0;j<wlen;++j)
          SRC[p + j] = w[j];
         out.pb(mp(5 , bput.se));
         add_info.pb(0);
                              }
   else{
    reverse(SRC + bflip.se.fi,
            SRC + bflip.se.se + 1);
    out.pb(mp(2 , bflip.se));
    add_info.pb(0);
       }
                      }
}
// Small cases solution
cut_state best_cut(){
  cut_state bst(0 , mp(mp(0,0),0));
  for(int i=0;i<N;++i)
   for(int j=i;j<N;++j)
    for(int p=0;p<N - (j-i+1);++p)
     relaxMin(bst , mp(apply_cut(i , j , p),
                       mp(mp(i , j) , p)));
  return bst;
}
void small_solve(){
  for(int i=0;i<T;++i){
   TRY_FLIPS = TRY_WORDS = BORDER = N;
   best_move();
   cut_state bcut = best_cut();
   if(bcut.fi < min(bflip.fi , bput.fi)){
    apply_cut(bcut.se.fi.fi , bcut.se.fi.se,
              bcut.se.se);
    memcpy(SRC , BUF , N*sizeof(char));
    out.pb(mp(1 , bcut.se.fi));
    add_info.pb(bcut.se.se);
                                        }
   else if(bput.fi < bflip.fi){
         char* w = WRD[bput.se.fi];
         int wlen = WRDL[bput.se.fi],
             p = bput.se.se;
         for(int j=0;j<wlen;++j)
          SRC[p + j] = w[j];
         out.pb(mp(5 , bput.se));
         add_info.pb(0);
                              }
   else{
    reverse(SRC + bflip.se.fi,
            SRC + bflip.se.se + 1);
    out.pb(mp(2 , bflip.se));
    add_info.pb(0);
       }
                      }
}
// </end>
void solve(){
  configure();
  #ifdef TESTING
  double beg = clock();
  #endif
  if(N <= 100 && T <= 20)
   small_solve();
  else
   iterate();
  #ifdef TESTING
  printf("%.3lf\n" , (clock() - beg)/CLOCKS_PER_SEC);
  #endif
}
int main(){
  read();
  #ifdef TESTING
  cout<<score()<<endl;
  #endif
  solve();
  #ifdef TESTING
  cout<<score()<<endl;
  #endif
  write();
  return 0;