#include <bits/stdc++.h>

using namespace std;

#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using pint = pair<int, int>;
using tint = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

int H, W, K, P;
int x[20], y[20];
string n[20];
int mas[33][33];

int dx[] = {1, 0};
int dy[] = {0, 1};

unsigned int dp[33][33];

unsigned int solve(int mx, int my, int bit) {
  if(mx == H && my == W) return 1;
  if(mx < 0 || H < mx || my < 0 || W < my) return 0;
  unsigned int& res = dp[mx][my];
  if(~res) return res;
  res = 0;
  rep(i, 2) {
    int nx = mx + dx[i], ny = my + dy[i];
    int id = mas[ny][nx];
    if(id == -1 || (bit>>id)&1) {
      res += solve(nx, ny, bit);
    }
  }
  return res;
}

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  cin >> H >> W >> K >> P;
  memset(mas, -1, sizeof(mas));
  rep(i, K) {
    cin >> x[i] >> y[i] >> n[i];
    mas[y[i]][x[i]] = i;
  }
  unsigned int ans = 0, bit = 0;
  rep(i, 1<<K) {
    if(__builtin_popcount(i) > P) continue;
    memset(dp, -1, sizeof(dp));
    unsigned int temp = solve(0, 0, i);
    if(temp > ans) {
      ans = temp;
      bit = i;
    }
  }
  cout << ans%mod << endl;
  rep(i, K) {
    if((bit>>i)&1) cout << n[i] << endl;
  }

  return 0;
}