// fixdna.cpp : Defines the entry point for the console application.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 20000
#define MAXV 50
#define MAXT 500000

int n,k,t,v;

int charDifference[MAXN][MAXN];

struct word
{
	int Len;
	char abc[100];
};

struct word pword[MAXV];
int cword=0;

struct oper
{
	int op;
	int ind;
	int left;
	int right;
	char letter;
};

struct oper poper[MAXT];
int coper=0;


char tempSequence[MAXN];


char startSequence[MAXN];
char targetSequence[MAXN];

bool flagPlace[MAXN];


int tempDICTindex;
int tempDICTpoints;

int tempREVleft;
int tempREVright;
int tempREVpoints;

int tempDIRleft;
int tempDIRright;
int tempDIRpoints;

int printDecision()
{
	printf("%d", coper);
	for (int j = 0; j<coper; j++)
	{
		if (poper[j].op == 1)
		{
			printf("\n1 %d %d %d", poper[j].left, poper[j].right, poper[j].ind);
		}
		if (poper[j].op == 2)
		{
			printf("\n2 %d %d", poper[j].left, poper[j].right);
		}
		if (poper[j].op == 3)
		{
			printf("\n3 %d", poper[j].ind);
		}
		if (poper[j].op == 4)
		{
			printf("\n4 %d %c", poper[j].ind, poper[j].letter);
		}
		if (poper[j].op == 5)
		{
			printf("\n5 %d %d", poper[j].ind, poper[j].left);
		}
	}

	return 0;

}


void DICTPoints(int a)
{
	
	//op 5 - речник
	poper[coper].op = 5;
	poper[coper].ind = tempDICTindex;
	poper[coper].left = a;
	coper++;
	//printf("op 5 - речник\n");
	//------------------
	for (int j = 0; j<pword[tempDICTindex].Len; j++)
		startSequence[a + j] = pword[tempDICTindex].abc[j];
	//------------------
	for (int j = a; j < n; j++)
		if (startSequence[j] == targetSequence[j])
			flagPlace[j] = true;
		else
			flagPlace[j] = false;

	//printf("%s\n", startSequence);
	//for (int j = 0; j < n; j++) printf("%d", flagPlace[j]);
	//printf("\n");
}
void eqDICT(int ii,int end)
{
	int tlen=end-ii+1;
	int tindex=-1;
	int tpoints=0;
	int tl;
	tempDICTindex=0;
	tempDICTpoints=0;
	
	for(int i=0;i<v;i++)
	{
		tl=0;
		if(tlen<pword[i].Len) continue;

		for(int j=0;j<pword[i].Len;j++)
		{
			if(pword[i].abc[j] == targetSequence[ii+j])
				tl+=1;
		}

		if(tl>tpoints)
		{
			tpoints=tl;
			tindex=i;
		}
	}
	tempDICTindex=tindex;
	tempDICTpoints=tpoints;
}

void DIRPoints(int a)
{

	//op 1 - преместване
	poper[coper].op = 1;
	poper[coper].left = tempDIRleft;
	poper[coper].right = tempDIRright;
	poper[coper].ind = a;
	coper++;
	//printf("op 1 - преместване\n");
	//------------------	
	int ttemp;
	int j;
	for (j = a, ttemp = 0; j < tempDIRleft; j++)
	{
		tempSequence[ttemp++] = startSequence[j];
	}
	for (j = 0; (tempDIRleft+j)<=tempDIRright; j++)
	{
		startSequence[a+j] = startSequence[tempDIRleft+j];
	}
	for (int f = 0; f < ttemp;f++, j++)
	{
		startSequence[a + j] = tempSequence[f];
	}


	//------------------				
	for (j = a; j < n; j++)
	if (startSequence[j] == targetSequence[j])
		flagPlace[j] = true;
	else
		flagPlace[j] = false;

	//printf("%s\n", startSequence);
}
void eqDIR(int ii,int end)
{
	int tleft=-1;
	int tright=-1;
	int tpoints=0;
	int tl=0;
	int z,s;

	for(int i=ii+1;i<end;i++)
	{
		tl = 0;
		for (int j = i,z=0; j <= end; j++,z++)
		{
			if (startSequence[j] == targetSequence[ii + z])
			{
				tl += 1;
				s = j;
			}
		}
		z = s - (ii - i);
		for (int j = ii,m=0; j < i; j++,m++)
		{
			if (startSequence[j] == targetSequence[m + z])
			{
				tl += 1;
				
			}
		}


		if(tl>tpoints)
		{
			tleft=i;
			tright=s;
			tpoints=tl;
		}
	}

	tempDIRleft=tleft;
	tempDIRright=tright;
	tempDIRpoints=tpoints;
}

void REVPoints(int a)
{

	//op 2 - обръщане
	poper[coper].op = 2;
	poper[coper].left = a;
	poper[coper].right = tempREVright;
	coper++;

	int ttemp = 0;
	for (int j = tempREVright; j >= a; j--)
	{
		tempSequence[ttemp++] = startSequence[j];
	}

	for (int j = 0; j < ttemp; j++)
	{
		startSequence[a + j] = tempSequence[j];
	}

	//------------------

	for (int j = a; j < n; j++)
	if (startSequence[j] == targetSequence[j])
		flagPlace[j] = true;
	else
		flagPlace[j] = false;

	//printf("%s\n", startSequence);
}
void eqREV(int ii,int end)
{
	int tleft=0;
	int tright=0;
	int tpoints=0;
	int tl;
	int j;
	int z;
	
	for(int d=end;d>ii;d--)
	{
		
		tl=0;
		for(j=d,z=0;j>ii;j--,z++)
		{
			if(startSequence[d-z] == targetSequence[ii+z])
			{
				tl+=1;
			}
		}
		
		if(tl>tpoints)
		{
			tleft=ii;
			tright=d;//z;
			tpoints=tl;
		}
	}
	
	
	tempREVleft=tleft;
	tempREVright=tright;
	tempREVpoints=tpoints;
	
}

void ChangePoints(int a)
{
	//op4 - добавяне на символ
	poper[coper].op = 4;
	poper[coper].ind = a;
	poper[coper].letter = targetSequence[a];
	coper++;
	//op3 - изтирване на символ
	poper[coper].op = 3;
	poper[coper].ind = a + 1;
	coper++;

	startSequence[a] = targetSequence[a];
	flagPlace[a] = true;

	//printf("%s\n", startSequence);
}


int main(int argc, char * argv[])
{
	freopen("fixdna.in","r",stdin);
	freopen("fixdna.out","w",stdout);

	scanf("%d %d %d\n",&n,&k,&t);
	scanf("%s\n",startSequence);
	scanf("%s",targetSequence);

	for(int i=0;i<n;i++)
	{
		if (startSequence[i]==targetSequence[i])
		{
			flagPlace[i] = true;
		}
		else
		{
			flagPlace[i] = false;
		}
			
	}

	for(int i=0;i<k;i++)
		for(int j=0;j<k;j++)
		{
			if(j==0)
			{
				scanf("\n");
			}
			
			if(j==(k-1))
			{
				scanf("%d\n",&(charDifference[i][j]));
			}
			else
			{
				scanf("%d ",&(charDifference[i][j]));
			}
		}
		
	scanf("%d\n",&v);
	for(int i=0;i<v;i++)
	{
		scanf("%s",pword[cword].abc);
		pword[cword].Len=strlen(pword[cword].abc);
		cword++;
		if(i<(v-1))
		{
			scanf("\n");
		}
	}

	int borderIndex=0;
	char tempC,w; 

	//printf("%s\n", targetSequence);
	//printf("%s\n", startSequence);

	for(int i=0;i<n;i++)
	{
		if(flagPlace[i]==true) continue;
		

		borderIndex=i;
		for(int j=i+1;j<n;j++)
		{
			if(flagPlace[j]==true) 
				break;
			else
				borderIndex++;
		}

		if (borderIndex == i)
		{
			int q = 0;

			for (int j = i; j<n; j++)
			{
				if (startSequence[j] == targetSequence[j])
				{
					q += 1;
				}
				
			}
			
			eqREV(i, n-1);
			eqDICT(i, i);
			if (tempDICTpoints = 0)
			{
				if (tempREVpoints > q)
				{
					if ((coper + 1) > t) return printDecision();
					REVPoints(i);

				}
				else
				{
					if ((coper + 2) > t) return printDecision();
					ChangePoints(i);
				}
				
				
			}
			else
			{
				if ((coper + 1) > t) return printDecision();

				if (tempREVpoints > tempDICTpoints)
				{		
					if (tempREVpoints > q)
					{
						REVPoints(i);
					}
					else
					{
						if ((coper + 2) > t) return printDecision();
						ChangePoints(i);
					}
				}
				else
				{
					
					if (tempDICTpoints > q)
					{
						DICTPoints(i);
					}
					else
					{
						if ((coper + 2) > t) return printDecision();
						ChangePoints(i);
					}
				}
			}
			
		}
		else
		{
			eqREV(i,borderIndex);
			eqDIR(i,borderIndex);
			eqDICT(i,borderIndex);
			
			if(tempREVpoints > tempDIRpoints)
			{
				if(tempREVpoints > tempDICTpoints)
				{
					if ((coper + 1) > t) return printDecision();
					REVPoints(i);
				}
				else
					if(tempDICTpoints > 0)
					{
						if ((coper + 1) > t) return printDecision();
						DICTPoints(i);
					}
			}
			else if(tempDIRpoints >= tempDICTpoints)
			{
				if (tempDIRpoints > 0)
				{
					if ((coper + 1) > t) return printDecision();
					DIRPoints(i);
				}
			}
			else
					if(tempDICTpoints > 0)
					{
						if ((coper + 1) > t) return printDecision();
						DICTPoints(i);
					}
		}

	}

	return printDecision();
}