#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

int H, W, K, P;
string S[20];
int x[20];
int y[20];
vector<int>box;
long long int ans=0;

void Search(vector<int>s) {
	long long int dis[33][33] = {};
	for (auto i : s) {
		if (!x[i] && !y[i])return;
	}
	dis[0][0] = 1;
	for (int i = 0; i <= H; i++){
		for (int j = 0; j <= W; j++) {
			if (i&&j) {
				bool flag = true;
				for (auto k : s) {
					if (i == y[k] && j == x[k])flag = false;
				}
				if (!flag)continue;
				dis[i][j] = dis[i][j - 1];
				dis[i][j] += dis[i - 1][j];
				//dis[i][j] %= MOD;
			}
			else if (i) {
				bool flag = true;
				for (auto k : s) {
					if (i == y[k] && j == x[k])flag = false;
				}
				if (!flag)continue;
				dis[i][j] = dis[i-1][j];
				//dis[i][j] %= MOD;
			}
			else if (j) {
				bool flag = true;
				for (auto k : s) {
					if (i == y[k] && j == x[k])flag = false;
				}
				if (!flag)continue;
				dis[i][j] = dis[i][j-1];
				//dis[i][j] %= MOD;
			}
			//cout << i<<" "<<j<<" "<<dis[i][j] << endl;
		}
	}
	//cout << dis[H][W] << endl;
	if (ans < dis[H][W]) {
		ans = max(ans, dis[H][W]);
		//cout << s.size() << endl;
		box = s;
	}
}

int main() {
	cin >> W >> H >> K >> P;
	for (int i = 0; i < K; i++) {
		cin >> x[i] >> y[i] >> S[i];
	//	cout << x[i] << y[i] << S[i] << endl;
	}
	for (int i = 0; i < (int)pow(2, K); i++) {
		int num = i;
		vector<int>bag;
		for (int j = 0; j < K; j++) {
			if (!(num % 2))bag.push_back(j);
			num /= 2;
		}
		if (bag.size() == K - P)Search(bag);
	}
	cout << ans%MOD << endl;
	// << box.size()<< endl;
	for (int j = 0; j < K; j++) {
		bool flag = true;
		for (auto i : box) {
			if (j != i)flag = false;
		}
		if(flag)cout << S[j] << endl;
	}
	return 0;
}