#pragma region Includes & Usings

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include <cstring>
#include <queue>
#include <climits>

using namespace std;

#pragma endregion

#pragma region Constants

#define MOVE 1
#define REVERSE 2
#define DELETE 3
#define INSERT 4
#define APPLY 5
#define REPLACE 6

const int MAX_N = 200000;
const int MAX_K = 26;
const int MAX_T = 15000;
const int MAX_V = 10;
const int MAX_WLEN = 100;

const float TIME_LIMIT = 7.75;
const int CHUNK_LEN = 5;

#pragma endregion

#pragma region Helper Classes & Structs

struct Oper
{
	int type;
	int arg1;
	int arg2;
	int arg3;

	Oper() { }
	Oper(int type, int arg1, int arg2=-1, int arg3=-1)
	{
		this->type = type;
		this->arg1 = arg1;
		this->arg2 = arg2;
		this->arg3 = arg3;
	}
};

struct OperWithProfit
{
	int profit;
	Oper* oper;

	OperWithProfit() { }
	OperWithProfit(int profit, Oper* oper)
	{
		this->profit = profit;
		this->oper = oper;;
	}
};

bool operator<(const OperWithProfit& first, const OperWithProfit& second)
{
	return first.profit < second.profit;
}

#pragma endregion

#pragma region Global Variables

int n, k, t, v;
char sseq[MAX_N], eseq[MAX_N];
int dif[MAX_K][MAX_K];
char words[MAX_V][MAX_WLEN];
Oper* result[MAX_T];
int oper_count;
clock_t start_time;

#pragma endregion

#pragma region Worker Methods

#pragma region Calc Helpers

int difference(char c1, char c2)
{
	return dif[c1-'a'][c2-'a'];
}

int rand(int max_value)
{
	return rand() % max_value;
}

int rand(int min_value, int max_value)
{
	return min_value + rand() % (max_value - min_value);
}

#pragma endregion

#pragma region Input, Output

void input()
{
	scanf("%d%d%d", &n, &k, &t);
	scanf("%s%s", &sseq, &eseq);
	for(int i=0; i<k; i++)
	{
		for(int j=0; j<k; j++)
		{
			scanf("%d", &dif[i][j]);
		}
	}
	scanf("%d", &v);
	for(int i=0; i<v; i++)
	{
		scanf("%s", &words[i]);
	}
}

void output()
{
	printf("%d\n", oper_count);
	for(int i=0; i<oper_count; i++)
	{
		switch(result[i]->type)
		{
			case MOVE:
				printf("%d %d %d %d\n", result[i]->type, result[i]->arg1, result[i]->arg2, result[i]->arg3);
				break;
			case REVERSE:
				printf("%d %d %d\n", result[i]->type, result[i]->arg1, result[i]->arg2);
				break;
			case DELETE:
				printf("%d %d\n", result[i]->type, result[i]->arg1);
				break;
			case INSERT:
				printf("%d %d %c\n", result[i]->type, result[i]->arg1, result[i]->arg2);
				break;
			case APPLY:
				printf("%d %d %d\n", result[i]->type, result[i]->arg1, result[i]->arg2);
				break;
		}
	}

	//int score = 0;
	//for(int i=0; i<n; i++)
	//{
	//	score += difference(sseq[i], eseq[i]);
	//}
	//printf("Score = %d\n", score);
}

#pragma endregion

#pragma region Real Execution of Opearations

void exec_operation(Oper* oper)
{
	switch(oper->type)
	{
		case MOVE:
		{
			char temp[MAX_N];
			int from = oper->arg1;
			int to = oper->arg2;
			int pos = oper->arg3;
			int len = to-from+1;
			if(pos < from)
			{
				memcpy(temp, sseq+from, len);
				memmove(sseq+pos+len, sseq+pos, from-pos);
				memcpy(sseq+pos, temp, len);
			}
			else
			{
				memcpy(temp, sseq+from, len);
				memmove(sseq+from, sseq+from+len, pos-from);
				memcpy(sseq+pos, temp, len);	
			}
			result[oper_count++] = oper;
			break;
		}
		case REVERSE:
		{
			int from = oper->arg1;
			int to = oper->arg2;
			char c;
			for(int i=from; i<(from+to)/2; i++)
			{
				c = sseq[i];
				sseq[i] = sseq[from+to-i];
				sseq[from+to-i] = c;
			}
			result[oper_count++] = oper;
			break;
		}
		case DELETE:
			break;
		case INSERT:
			break;
		case APPLY:
		{
			char* word = words[oper->arg1];
			int len = strlen(word);
			int from = oper->arg2;
			strncpy(sseq+from, word, len);
			result[oper_count++] = oper;
			break;
		}
		case REPLACE:
			result[oper_count++] = new Oper(DELETE, oper->arg1);
			sseq[oper->arg1] = oper->arg2;
			result[oper_count++] = new Oper(INSERT, oper->arg1, oper->arg2);
			break;
	}
}

#pragma endregion

#pragma region Greedy Selection of Best Operation

#pragma region eval_profit
int eval_profit(Oper* oper)
{
	int res = 0;
	switch(oper->type)
	{
		case MOVE:
		{
			char tseq[MAX_N];
			strcpy(tseq, sseq);

			char temp[MAX_N];
			int from = oper->arg1;
			int to = oper->arg2;
			int pos = oper->arg3;
			int len = to-from+1;
			if(pos < from)
			{
				memcpy(temp, tseq+from, len);
				memmove(tseq+pos+len, tseq+pos, from-pos);
				memcpy(tseq+pos, temp, len);
			}
			else
			{
				memcpy(temp, tseq+from, len);
				memmove(tseq+from, tseq+from+len, pos-from);
				memcpy(tseq+pos, temp, len);	
			}
			for(int i=min(from, pos); i<=max(from, pos)+len; i++)
			{
				res += difference(sseq[i], eseq[i]);
				res -= difference(tseq[i], eseq[i]);
			}

			break;
		}
		case REVERSE:
		{
			int from = oper->arg1;
			int to = oper->arg2;
			for(int i=from; i<=to; i++)
			{
				res += difference(sseq[i], eseq[i]);
				res -= difference(sseq[i], eseq[from+to-i]);
			}
			break;
		}
		case DELETE:
			break;
		case INSERT:
			break;
		case APPLY:
		{
			char* word = words[oper->arg1];
			int len = strlen(word);
			int from = oper->arg2;
			for(int i=0; i<len; i++)
			{
				res += difference(sseq[from+i], eseq[from+i]);
				res -= difference(word[i], eseq[from+i]);
			}
			break;
		}
		case REPLACE:
			res = difference(sseq[oper->arg1], eseq[oper->arg1]);
			break;
	}
	return res;
}
#pragma endregion

#pragma region best_apply
OperWithProfit* best_apply()
{
	OperWithProfit* result = new OperWithProfit(0, new Oper(APPLY, 0, 0));

	for(int i=0; i<v; i++)
	{
		int len = strlen(words[i]);
		for(int j=0; j<=n-len; j++)
		{
			float runtime = ((float)clock() - (float)start_time) / CLOCKS_PER_SEC;
			if(runtime > TIME_LIMIT)
			{
				return NULL;
			}

			int cur = eval_profit(new Oper(APPLY, i, j));
			if(cur > result->profit)
			{
				result->profit = cur;
				result->oper->arg1 = i;
				result->oper->arg2 = j;
			}
		}
	}
	return result;
}
#pragma endregion

#pragma region best_reverse
OperWithProfit* best_reverse()
{
	OperWithProfit* result = new OperWithProfit(0, new Oper(REVERSE, 0, 0));

	for(int i=0; i<n; i++)
	{
		for(int j=i+1; j<n; j++)
		{
			float runtime = ((float)clock() - (float)start_time) / CLOCKS_PER_SEC;
			if(runtime > TIME_LIMIT)
			{
				return NULL;
			}

			int cur = eval_profit(new Oper(REVERSE, i, j));
			if(cur > result->profit)
			{
				result->profit = cur;
				result->oper->arg1 = i;
				result->oper->arg2 = j;
			}
		}
	}

	return result;
}
#pragma endregion

#pragma region best_move
OperWithProfit* best_move()
{
	OperWithProfit* result = new OperWithProfit(0, new Oper(MOVE, 0, 0));

	for(int i=0; i<n; i++)
	{
		for(int j=i+1; j<n; j++)
		{
			for(int pos=0; pos<i; pos++)
			{
				float runtime = ((float)clock() - (float)start_time) / CLOCKS_PER_SEC;
				if(runtime > TIME_LIMIT)
				{
					return NULL;
				}

				Oper* oper = new Oper(MOVE, i, j, pos);
				int profit = eval_profit(oper);
				if(profit > result->profit)
				{
					result->profit = profit;
					result->oper = oper;
				}
			}
		}
	}

	return result;
}
#pragma endregion

#pragma region best_oper
OperWithProfit* best_oper()
{
	OperWithProfit* result = best_apply();
	OperWithProfit* oper = best_move();
	if(oper != NULL && oper->profit > result->profit)
	{
		result = oper;
		oper = best_reverse();
		if(oper != NULL && oper->profit > result->profit)
		{
			result = oper;
		}
	}
	return result;
}
#pragma endregion

#pragma region best_heuristics
OperWithProfit* best_heuristics(int turn)
{
	if(turn == 0 && n>1000)
	{
		const int ITERATIONS = 10;
		OperWithProfit* result = new OperWithProfit(0, new Oper(MOVE, 0, 0, 0));
		for(int i=0; i<ITERATIONS; i++)
		{
			Oper* oper = new Oper(MOVE, rand(100, 200), rand(300, 400), rand(1, 100));
			int profit = eval_profit(oper);
			if(profit > result->profit)
			{
				result->profit = profit;
				result->oper = oper;
			}
		}
		return result;
	}
	else
	{
		return best_apply();
	}
}

#pragma endregion

#pragma region Fill-in Allowed Turns With Replaces
void execute_replaces(int current_operation_index)
{
	priority_queue<OperWithProfit> replaces;
	for(int j=0; j<n; j++)
	{
		OperWithProfit replace = *new OperWithProfit(difference(sseq[j], eseq[j]), new Oper(REPLACE, j));
		replaces.push(replace);
	}

	for(int j=current_operation_index; j<t-1; j+=2)
	{
		OperWithProfit replace = replaces.top();
		replaces.pop();
		exec_operation(new Oper(REPLACE, replace.oper->arg1, eseq[replace.oper->arg1]));
	}
}
#pragma endregion

#pragma region Calculations Dispatch
OperWithProfit* select_proper_operation(int turn)
{
	if(n<=100 && t<=20 && v<=5)
	{
		return best_oper();
	}
	else if(v == 0)
	{
		return best_reverse();
	}
	else if(n<=5000 && t<=500 && v<=10)
	{
		return best_apply();
	}
	else if(n<=20000 && k<=15 && t<=1000 && v<=25)
	{
		return best_apply();
	}
	else
	{	
		return best_heuristics(turn);
	}
}
#pragma endregion

void calc()
{
	for(int i=0; i<t; i++)
	{
		OperWithProfit* operWithProfit = select_proper_operation(i);

		if(operWithProfit != NULL && operWithProfit->profit > 0)
		{
			exec_operation(operWithProfit->oper);
		}
		else
		{
			execute_replaces(i);
			return;
		}
	}
}

#pragma endregion

#pragma region Main

int main()
{
	start_time = clock();

	freopen("fixdna.in", "r", stdin);
	freopen("fixdna.out", "w", stdout);

	input();

	calc();

	output();

	return 0;
}

#pragma endreg