#include <bits/stdc++.h>
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
#define int long long
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
const int INF = 1e9;

int H, W, K, P;
int x[20], y[20];
string N[20];
int dp[40][40];
bool can_move[40][40];  //通れないところはfalse

signed main()
{
    cin >> H >> W >> K >> P;
    REP(i,K) cin >> x[i] >> y[i] >> N[i];

    int ma = 0;
    vector<string> ans;
    for (int i=0; i<(1<<K); i++) {
        //ビットが立っているところは通れない
        if (__builtin_popcount(i) != K - P) continue;

        REP(j,40) REP(k,40) can_move[j][k] = true;
        REP(j,K) if (i >> j & 1) can_move[x[j]][y[j]] = false;

        for (int x=0; x<=H; x++) {
            for (int y=0; y<=W; y++) {
                dp[x][y] = (x == 0 && y == 0 ? 1 : 0);
                if (0 <= x - 1) dp[x][y] += dp[x-1][y];
                if (0 <= y - 1) dp[x][y] += dp[x][y-1];
                if (!can_move[x][y]) dp[x][y] = 0;
            }
        }

        if (ma < dp[H][W]) {
            ma = dp[H][W];
            ans.clear();
            REP(j,K) if (~i >> j & 1) ans.push_back(N[j]);
        }
    }

    cout << ma % MOD << endl;
    REP(i,ans.size()) cout << ans[i] << endl;
}