#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)< pii; typedef vector vi; typedef vector 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 (!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 X = 0; rep(S, 1 << K) { ll y = f(S); if (y > ans) { ans = y; X = S; } } cout << ans << endl; rep(i, K) { if (X >> i & 1) { cout << N[i] << endl; } } } }