#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <climits>

using namespace std;
const long long inf = 9e18;
const int mod = 1e9 + 7;

int h, w, k, p;
vector<int> x, y;

void check() {
	w = 32;
	h = 32;
	vector<vector<long long>> board(h+1, vector<long long>(w+1, 0));

	for (int i = 0; i <= h; i++) {
		board[i][0] = 1;
	}
	for (int i = 0; i <= w; i++) {
		board[0][1] = 1;
	}

	for (int i = 1; i <= h; i++) {
	for (int j = 1; j <= w; j++) {
		board[i][j] += board[i-1][j] + board[i][j - 1];
		printf("%2d %2d: %20llu\n", i, j, board[i][j]);
	}}
}

long long calc(int ok_bits) {
	// 東西方向にHメートル、南北方向にWメートル
	vector<vector<long long>> board(w+2, vector<long long>(h+2, 0));
	board[0][0] = 1;

	// vector<string> aaa(w+1, string(h+1, '.'));

	for (int i = 0; i < k; i++) {
		if ((ok_bits >> i) & 1) {
			continue;
		}
		board[y[i]][x[i]] = -inf;
		// aaa[y[i]][x[i]] = 'x';
	}

	for (int i = 0; i <= w; i++) {
	for (int j = 0; j <= h; j++) {
		if (board[i][j] > 0) {
			board[i+1][j] += board[i][j];
			board[i][j+1] += board[i][j];
		}
	}}

	// for (auto s : aaa) {
	// 	cout << s << endl;
	// }

	return max(board[w][h], 0LL);

}

int main() {
	cin >> h >> w >> k >> p;

	x.assign(k, 0);
	y.assign(k, 0);
	vector<string> name(k);
	for (int i = 0; i < k; i++) {
		cin >> x[i] >> y[i] >> name[i];
	}

	long long ans = 0;
	int store = 0;
	for (int i = 0; i < (1 << k); i++) {
		if (__builtin_popcount(i) != p) {
			continue;
		}
		auto val = calc(i);
// printf("%5d: %20lld, %20lld\n", i, val, val % mod);
		if (val > ans) {
			ans = val;
			store = i;
		}
	}

	ans %= mod;
	cout << ans << endl;
	for (int i = 0; i < k; i++) {
		if ((store >> i) & 1) {
			cout << name[i] << endl;
		}
	}
	return 0;
}