#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

#define MAXN 20000
#define MAXT 15000
#define REAL_MAXN 200000

#define NONE -1

#define MAXV 50
#define MAXVLEN 100

//#define NUM_SKELETONS 61
#define POPULATION_SIZE 10
#define CHILDREN_PER_SOLUTION 300
#define NUM_SKELETONS POPULATION_SIZE+CHILDREN_PER_SOLUTION+1
#define MAX_CHAR_DIFF0 40
#define MAX_CHAR_DIFF 50

#define SIMULATION_TIME 7700
#define STUPID_TIME 7200

#define STUPID_NEEDED_PTS 20

int GROUP;
int MAX_UNITS_PER_GROUP[4]={100,50,20,5};

int GENERATIONS;
int MAX_UNITS;
const int OFFSPRING = 50;

int N,K,V,T;
char words[MAXV][MAXVLEN];
int wordLen[MAXV];
int wordIdx[MAXV];

int charDiff[26][26];
char targetStr[REAL_MAXN+5];
char startingStr[REAL_MAXN+5];


// (0) a - move substring
// (1) b - reverse substring
// (2) c - remove character
// (3) d - insert character
// (4) e - apply dict string
const char types[5]={'a','b','c','d','e'};

const int AVAILABLE_ACTIONS[3]={0,1,4};

struct Operation { char type; Operation *prevOp; int p1,p2,p3; Operation(); void set(int,int,int,int); }; 
Operation :: Operation () { prevOp = NULL; }

void Operation :: set (int t, int _p1, int _p2=-1, int _p3=-1)
{
	type = types[t]-'a';
	p1=_p1; p2=_p2; p3=_p3;
}

int opN=0;
Operation op[500000];

Operation *getOp() { return &op[opN++]; }

struct Solution
{
	int operationsUsed,unfitness;
	Operation *newOp;
	char str[MAXN+5];
	
	bool alive,reserved;
	
	Solution();
	void set(Solution*,bool);
	void calcUnfitness();
	void printFinal();
} sol[NUM_SKELETONS];
int solN=0;

Solution :: Solution () { alive=reserved=false; newOp=NULL; operationsUsed=0; }

void Solution :: calcUnfitness()
{
	unfitness=0;
	
	int cnt[MAX_CHAR_DIFF0+1];
	for(int i=0; i<=MAX_CHAR_DIFF0; i++) cnt[i]=0;
	for(int i=0; i<N; i++)
	{
		unfitness += charDiff[str[i]-'a'][targetStr[i]-'a'];
		cnt[charDiff[str[i]-'a'][targetStr[i]-'a']]++;
	}
	int opLeft=(T-operationsUsed)/2, t;
	for(int i=MAX_CHAR_DIFF0; i>=0; i--)
	{
		t = min(opLeft, cnt[i]);
		opLeft-=t; unfitness-=i*t;
	}
}
void Solution :: printFinal()
{
	vector<int> emptyVector;
	vector< vector<int> > idxs(MAX_CHAR_DIFF0+1, emptyVector);
	for(int i=0; i<N; i++)
	{
		idxs[charDiff[str[i]-'a'][targetStr[i]-'a']].push_back(i);
	}
	int opLeft=(T-operationsUsed)/2, t;
	while(opLeft)
	{
		for(int i=MAX_CHAR_DIFF0; i>=0; i--)
		{
			t = min(opLeft, (int)(idxs[i].size()));
			opLeft-=t;
			for(int j=0; j<t; j++)
			{
				printf("%d %d\n", 3, idxs[i][j]);
				printf("%d %d %c\n", 4, idxs[i][j], targetStr[idxs[i][j]]);
				str[idxs[i][j]] = targetStr[idxs[i][j]];
			}
		}
	}
}

void setStr(char target[], char from[], int a1, int b1, int a2, int b2, int a3, int b3, int a4, int b4)
{
	int idx=0;
	for(int i=a1; i<=b1; i++) target[idx++]=from[i];
	for(int i=a2; i<=b2; i++) target[idx++]=from[i];
	for(int i=a3; i<=b3; i++) target[idx++]=from[i];
	for(int i=a4; i<=b4; i++) target[idx++]=from[i];
}

void Solution :: set(Solution *from, bool f=false)
{
	//printf("setting...\n");
	//O(N)
	int t,p1,p2,p3,p4,a,len,idx=0;
	t = AVAILABLE_ACTIONS[rand()%3];
	if(t==4 and V==0) t=rand()%2;
	if(f) t=1;
	//printf("Setting solution... %d\n", t);
	newOp = getOp();
	
	
	if(t==0)
	{
		len = (rand()%(N-1)) + 1;
		p1 = rand()%(N - len + 1);
		p2 = p1+len-1;
		p3 = rand()%(N - len);
		if(p3>=p1) p3++; //moving a substring to the same place it is at is pointless
		p4 = p3+len-1;
		
		if(p3 < p1) setStr(str, from->str,  0,p3-1,  p1,p2,  p3,p1-1,  p2+1,N-1);
		else setStr(str, from->str,  0,p1-1,  p2+1,p4,  p1,p2,  p4+1,N-1);
		
		newOp -> set(t,  p1,p2,  p3);
	}
	else if(t==1)
	{
	//printf("%d %d\n", N, len);
		len = (rand()%(N-1)) + 1;
		p1 = rand()%(N - len + 1);
		p2 = p1+len-1;
		
		if(f) { p1=0; p2=N-1; }
		
		for(int i=0; i<p1; i++) str[idx++]=from->str[i];
		for(int i=p2; i>=p1; i--) str[idx++]=from->str[i];
		for(int i=p2+1; i<N; i++) str[idx++]=from->str[i];
		newOp -> set(t,  p1,p2);
	}
	else if(t==4)
	{
		p1 = rand()%V;
		len = wordLen[p1];
		p2 = rand()%(N - len + 1);
		p3 = p2+len-1;
		//printf("%d %d %d %d\n", p1, len, p2, p3);
		for(int i=0; i<p2; i++) str[idx++]=from->str[i];
		for(int i=0; i<len; i++) str[idx++]=words[p1][i];
		for(int i=p3+1; i<N; i++) str[idx++]=from->str[i];
		newOp -> set(t,  wordIdx[p1], p2);
	}
	
	newOp -> prevOp = from->newOp;
	operationsUsed = from->operationsUsed + 1;
	alive = true;
	
	calcUnfitness();
}

int bestSolution=NONE;

void init()
{
	scanf("%d %d %d", &N, &K, &T);
	scanf("%s %s", startingStr, targetStr);
	
	for(int i=0; i<K; i++) for(int j=0; j<K; j++) scanf("%d", &charDiff[i][j]);
	
	if(N>20000) return;
	
	strcpy(sol[NUM_SKELETONS-1].str,  startingStr);
	
	sol[NUM_SKELETONS-1].alive=true; sol[NUM_SKELETONS-1].calcUnfitness();
	solN++;
	
	
	sol[0].set(sol+NUM_SKELETONS-1, true);
	solN++;
	
	bestSolution = (sol[0].unfitness < sol[NUM_SKELETONS-1].unfitness) ? 0 : NUM_SKELETONS-1;
}

int trim()
{
	int worst=0;
	for(int i=0; i<NUM_SKELETONS; i++)
		if(sol[i].alive)
			if(sol[worst].alive == false or sol[i].unfitness > sol[worst].unfitness)
				worst=i;
	sol[worst].alive=false;
	solN--;
}

int getBest()
{
	int best=0;
	for(int i=1; i<NUM_SKELETONS; i++)
		if(sol[i].alive)
			if(sol[best].alive == false or sol[i].unfitness < sol[best].unfitness)
				best=i;
	if(sol[best].alive == false) return -1;
	return best;
}

void populate(int idx)
{
	int c=0;
	//for(int i=0; i<NUM_SKELETONS; i++) if(!sol[i].alive) c++;
	//printf("dead: %d\n", c);
	//printf("Populating... %d %d %d\n", solN, idx, c);
	
	Solution *parent = &sol[idx];
	
	
	if(bestSolution == NONE or sol[idx].unfitness < sol[bestSolution].unfitness) bestSolution = idx;
	
	int children=0;
	
	if(parent->operationsUsed < T)
	{
		for(int i=0; i<NUM_SKELETONS; i++)
		{
			if(!sol[i].alive and i!=bestSolution)
			{
				//printf("roar\n");
				sol[i].set(parent);
				children++;
				solN++;
				if(solN > POPULATION_SIZE) trim();
			}
			if(clock() >= SIMULATION_TIME) break;
			if(children >= CHILDREN_PER_SOLUTION)
			{
				break;
			}
		}
	}
	parent->alive = false;
	solN--;
}

void solve()
{
	int idx;
	while(clock() < SIMULATION_TIME)
	{
		if(bestSolution != NONE and sol[bestSolution].unfitness == 0) return;
		idx = getBest();
		if(idx == -1) return;
		populate(idx);
	}
}

void printOperations(Operation *o)
{
	if(o==NULL) return;
	printOperations(o->prevOp);
	if(o->type == 0) printf("%d %d %d %d\n", 1, o->p1, o->p2, o->p3);
	else if(o->type == 1) printf("%d %d %d\n", 2, o->p1, o->p2);
	else if(o->type == 4) printf("%d %d %d\n", 5, o->p1, o->p2);
	else printf("type = %d\n", o->type);
}

void printBestSolution()
{
	Solution *s = &sol[bestSolution];
	//printf("->>>> %s (%d)\n", s->str, s->unfitness);
	printf("%d\n", ((T - s->operationsUsed)&1) == 0 ? T : T-1);
	printOperations(s->newOp);
	s->printFinal();
	//printf("->>>> %s (%d)\n", s->str, s->unfitness);
}

int opLeft[2];
char s[2][REAL_MAXN+5];

vector< vector< vector<int> > > idxs;
int score[2];
int appliedN[2]={0,0};
int applied[2][MAXT][2];

int curIdx=0;

void tryOperation()
{
	//O(wordLen)
	if(opLeft[curIdx])
	{
		int idx=rand()%V, len=wordLen[idx], pos=rand()%(N - len + 1), to=pos+len-1;
		int a=0,b=0;
		for(int i=pos; i<=to; i++)
		{
			a += charDiff[s[curIdx][i]-'a'][targetStr[i]-'a'];
			b += charDiff[words[idx][i-pos]-'a'][targetStr[i]-'a'];
		}
		if(a-b >= STUPID_NEEDED_PTS)
		{
			for(int i=pos; i<=to; i++) s[curIdx][i]=words[idx][i-pos];
			applied[curIdx][appliedN[curIdx]][0] = wordIdx[idx];
			applied[curIdx][appliedN[curIdx]++][1] = pos;
			
			opLeft[curIdx]--;
		}
	}
	
	curIdx = (curIdx+1)&1;
}

void solveStupid()
{
	opLeft[0]=T; opLeft[1]=T-1;
	
	vector<int> emptyVector;
	vector< vector<int> > idxs0(MAX_CHAR_DIFF+1, emptyVector);
	for(int i=0; i<2; i++) idxs.push_back(idxs0);
	
	for(int i=0; i<N; i++)
	{
		s[0][i] = startingStr[i];
		s[1][i] = startingStr[N-i-1];
		for(int j=0; j<2; j++)
		{
			//idxs[j][charDiff[s[j][i]-'a'][targetStr[i]-'a']].push_back(i);
			//score[j] += charDiff[s[j][i]-'a'][targetStr[i]-'a'];
		}
	}
	
	while(clock() < STUPID_TIME and (opLeft[0] + opLeft[1] > 0))
	{
		tryOperation();
	}
	
	int t;
	for(int i=0; i<2; i++)
	{
		for(int j=0; j<N; j++)
		{
			idxs[i][charDiff[s[i][j]-'a'][targetStr[j]-'a']].push_back(j);
			score[i] += charDiff[s[i][j]-'a'][targetStr[j]-'a'];
		}
		t = opLeft[i]/2;
		for(int j=MAX_CHAR_DIFF; j>=0 and t; j--)
		{
			score[i] -= min(t, (int)(idxs[i][j].size()))*j;
			t -= min(t, (int)(idxs[i][j].size()));
		}
	}
	
	int idx = (score[0] < score[1]) ? 0 : 1;
	
	t = opLeft[idx]/2;
	printf("%d\n", t*2 + appliedN[idx] + (idx==1));
	if(idx==1) printf("2 %d %d\n", 0, N-1);
	
	for(int i=0; i<appliedN[idx]; i++) printf("5 %d %d\n", applied[idx][i][0], applied[idx][i][1]);
	
	for(int i=MAX_CHAR_DIFF; i>=0 and t; i--)
	{
		for(int j=0; j<idxs[idx][i].size() and t; j++)
		{
			printf("3 %d\n", idxs[idx][i][j]);
			printf("4 %d %c\n", idxs[idx][i][j], targetStr[idxs[idx][i][j]]);
			t --;
		}
	}
	
	//printf(">>> %d\n", min(a1,a2));
}

void init1()
{
	scanf("%d", &V);
	int idx=0;
	for(int i=0; i<V; i++) 
	{
		scanf("%s", words[i]);
		wordLen[i] = strlen(words[i]);
		wordIdx[i] = idx++;
		if(wordLen[i] > N)
		{
			i--; V--;
		}
	}
}

int main() 
{
	freopen("fixdna.in", "r", stdin);
	//freopen("fixdna.000.in", "r", stdin);
	freopen("fixdna.out", "w", stdout);
	srand(0);
	
	//printf("Init...\n");
	init();
	
	init1();
	
	//printf("Solving...\n");
	
	if(N>20000)
	{
		solveStupid();
	}
	else
	{
		solve();
		printBestSolution();
	}
	//printf("Printing...\n");
	
	
	
	return 0;