#include "bits/stdc++.h"
using namespace std;
#define FOR(i,j,k) for(int (i)=(j);(i)<(int)(k);++(i))
#define rep(i,j) FOR(i,0,j)
#define each(x,y) for(auto &(x):(y))
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(),(x).end()
#define debug(x) cout<<#x<<": "<<(x)<<endl
#define smax(x,y) (x)=max((x),(y))
#define smin(x,y) (x)=min((x),(y))
#define MEM(x,y) memset((x),(y),sizeof (x))
#define sz(x) (int)(x).size()
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;

int H, W, K, P;

int bitcnt(unsigned int x) {
    x = (x & 0x55555555) + (x >> 1 & 0x55555555);
    x = (x & 0x33333333) + (x >> 2 & 0x33333333);
    x = (x & 0x0f0f0f0f) + (x >> 4 & 0x0f0f0f0f);
    x = (x & 0x00ff00ff) + (x >> 8 & 0x00ff00ff);
    x = (x & 0x0000ffff) + (x >> 16 & 0x0000ffff);
    return (int)x;
}

const int DY[] = { -1,0,1,0 };
const int DX[] = { 0,1,0,-1 };

const int INF = INT_MAX / 3;
int bl[35][35];
ll wa[35][35];
int X[15], Y[15];
string N[15];

ll f(int S) {
    MEM(bl, 0);
    if (bitcnt(S) != P)return 0;
    rep(i, K) {
        if (!(S >> i & 1))bl[X[i]][Y[i]] = 1;
    }
    
    if (bl[0][0])return 0;
    MEM(wa, 0);
    
    wa[0][0] = 1;
    rep(y, H+1)rep(x, W+1) {
        rep(i, 4) {
            int ny = DY[i] + y, nx = DX[i] + x;
            if (ny>=0&&nx>=0&&!bl[ny][nx]) {
                wa[ny][nx] += wa[y][x];
            }
        }
    }
    return wa[H][W];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    while (cin >> H >> W >> K >> P) {
        rep(i, K)cin >> X[i] >> Y[i] >> N[i];
        ll ans = 0;
        int A = 0;
        rep(S, 1 << K) {
            ll y = f(S);
            if (y > ans) {
                ans = y;
                A = S;
            }
        }
        cout << ans %(int)(1e9+7) << endl;
        rep(i, K) {
            if (A >> i & 1) {
                cout << N[i] << endl;
            }
        }
    }
}