#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{
    freopen("fixdna.in","r",stdin);
    freopen("fixdna.out","w",stdout);
    int len_s,len_a,num_op,alphabet[30][30],i,j,num_words,br=0,final_br=0,t[15000][3];
    string current, target,dict[60],let[15000];
    scanf("%d%d%d",&len_s,&len_a,&num_op);
    cin>>current>>target;
    for (i=0;i<len_a;i++)
        for (j=0;j<len_a;j++)
        scanf("%d",&alphabet[i][j]);
    scanf("%d",&num_words);
    for (i=0;i<num_words;i++)
        cin>>dict[i];
    j=0;i=0;
    /*while (i<num_words&&final_br<num_op)
    {
        int tempCurSum=0,tempTargSum=0,tempWordSum=0,l;

        int u=l,y;
        for (l=0;l<len_s-dict[i].size()+1;l++)
        {for (y=0;y<dict[i].size();y++)
            {tempWordSum+=alphabet[int(target[i]-'a')][int(dict[i][y]-'a')];
            tempCurSum+=alphabet[int(target[y]-'a')][int(current[y]-'a')];u++;}if (tempWordSum<tempCurSum)
            {cout<<tempWordSum<<" "<<tempCurSum<<"\n";
                t[j][0]=5;t[j][1]=i;t[j][2]=l;final_br++;int k;
                for(k=0;k<dict[i].size();k++) {current[l+k]=dict[i][k];}
                j++;
            }if(final_br==num_op) break;
           // cout<<tempCurSum<<" "<<l<<" "<<u<<" "<<u-dict[i].size()+1<<" "<<u-dict[i].size()<<endl;
        //tempCurSum=tempCurSum+alphabet[int(target[l]-'a')][int(current[u]-'a')]-alphabet[int(target[u-dict[i].size()+1]-'a')][int(current[u-dict[i].size()]-'a')];
         }
        i++;
    }**/
    i=0;
    while (i<len_s-1&&final_br<num_op)
    {
        int tempTarget=int(target[i]-'a'),tempTarget1=int(target[i+1]-'a'),tempCurrent=int(current[i]-'a'),tempCurrent1=int(current[i+1]-'a');
        if (alphabet[tempTarget][tempCurrent1]<alphabet[tempTarget][tempCurrent]&&alphabet[tempTarget1][tempCurrent]<alphabet[tempTarget1][tempCurrent1])
                {t[j][0]=2;t[j][1]=i;t[j][2]=i+1;final_br++;j++;swap(current[i],current[i+1]);
            }i++;}
    if (i<len_s){
    if ((num_op-final_br)%2!=0) {j--;final_br--;}
    for (i=0;i<len_s&&j<num_op;i++)
            if (current[i]!=target[i])
            {
                current[i]=target[i];
                t[j][0]=3;t[j][1]=i;
                t[j+1][0]=4;t[j+1][1]=i;let[j+1]=target[i];j+=2;final_br+=2;
            }

    }
    printf("%d\n",final_br);
    for (i=0;i<final_br;i++)
        if (t[i][0]==3) cout<<t[i][0]<<" "<<t[i][1]<<endl;
        else if (t[i][0]==2||t[i][0]==5) cout<<t[i][0]<<" "<<t[i][1]<<" "<<t[i][2]<<endl;
        else cout<<t[i][0]<<" "<<t[i][1]<<" "<<let[i]<<endl;

}