# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 # define int long long
# define lc u << 1
# define rc u << 1 | 1
# define fi first
# define se second
const int N = 55, mod = 1e9 + 7;

int n, m, k, p;
struct node
{
	int x, y;
	string nm;
} a[N];
int f[N][N];
signed main ()
{
//	freopen ("kart.in", "r", stdin); freopen ("kart.out", "w", stdout);
	scanf ("%lld%lld%lld%lld", &n, &m, &k, &p); 
	for (int i = 0; i < k; i ++ ) cin >> a[i].x >> a[i].y >> a[i].nm;
	int ans = 0; vector <int> res;
	for (int s = 0; s < (1 << k); s ++ )
	{
		if (__builtin_popcount (s) != p) continue;
		memset (f, 0, sizeof f);
		vector <int> chs;
		for (int i = 0; i < k; i ++ )
		{
			if (!(s >> i & 1)) f[a[i].x][a[i].y] = -1;
			else chs.push_back (i);
		}
		f[0][0] = 1;
		for (int i = 0; i < n + 1; i ++ )
		{
			for (int j = 0; j < m + 1; j ++ )
			{
				if (f[i][j] == -1) continue;
				if (~f[i + 1][j]) f[i + 1][j] = (f[i + 1][j] + f[i][j]) % mod;
				if (~f[i][j + 1]) f[i][j + 1] = (f[i][j + 1] + f[i][j]) % mod;
			}
		}
		if (ans < f[n][m]) ans = f[n][m] % mod, res = chs;
	}
	printf ("%lld\n", ans);
	for (auto x : res) cout << a[x].nm << "\n";
	return 0;
}