#include <bits/stdc++.h>
using namespace std;

#define FOR(i,l,r) for(int i = (int) (l);i < (int) (r);i++)
#define ALL(x) x.begin(),x.end()
template<typename T> bool chmax(T& a,const T& b){ return a < b ? (a = b,true) : false; }
template<typename T> bool chmin(T& a,const T& b){ return b < a ? (a = b,true) : false; }
typedef long long ll;

int H,W,K,P;
vector<int> X,Y;
vector<string> name;
ll memo [100] [100];
const ll MOD = 1e9 + 7;

int bit_count(int x)
{
	int res = 0;
	for(;x;x -= x & -x) res++;
	return res;
}

ll rec(ll y,ll x,set< pair<int,int> >& st)
{
	if(st.count(make_pair(y,x))) return 0ll;
	if(memo [y] [x] != -1) return memo [y] [x];
	ll res = 0;
	if(y) res += rec(y - 1,x,st);
	if(x) res += rec(y,x - 1,st);
	return memo [y] [x] = res;
}

int main()
{
	cin >> H >> W >> K >> P;
	X.assign(K,0);
	Y.assign(K,0);
	name.assign(K,"");
	FOR(i,0,K){
		cin >> X [i] >> Y [i] >> name [i];
	}
	ll mx = 0;
	vector<string> ans;
	FOR(i,0,1 << K) if(bit_count(i) == P){
		memset(memo,-1,sizeof(memo));
		memo [0] [0] = 1;
		set< pair<int,int> > st;
		FOR(j,0,K) if((i >> j & 1) == 0){
			st.insert(make_pair(Y [j],X [j]));
		}
		if(chmax(mx,rec(W,H,st))){
			ans.clear();
			FOR(j,0,K) if(i >> j & 1){
				ans.push_back(name [j]);
			}
		}
	}

	cout << mx % MOD << endl;
	FOR(i,0,ans.size()){
		cout << ans [i] << endl;
	}

	return 0;
}