#include #include using namespace std; using ll = long long; int bitcount(int a){ int r = 0; while(a){ a -= a & -a; r++; } return r; } int main(){ int h, w, k, p, ans = -1; cin >> h >> w >> k >> p; ll maxi = -1; int x[k], y[k]; string n[k]; for(int i = 0; i < k; i++) cin >> x[i] >> y[i] >> n[i]; for(int puni = 0; puni < 1 << k; puni++){ if(p < bitcount(puni)) continue; ll dp[h + 1][w + 1]; fill(dp[0], dp[h + 1], -1); for(int i = 0; i < h + 1; i++) dp[i][0] = 1; for(int i = 0; i < w + 1; i++) dp[0][i] = 1; for(int i = 0; i < k; i++) if(!(puni >> i & 1)) dp[x[i]][y[i]] = 0; for(int i = 1; i < h + 1; i++) for(int j = 1; j < w + 1; j++) if(dp[i][j]){ dp[i][j] = max(dp[i][j], dp[i - 1][j] + dp[i][j - 1]); } if(maxi < dp[h][w]){ maxi = dp[h][w]; ans = puni; } } if(maxi == -1){ cout << 0 << endl; return 0; } cout << maxi % ll(1e9 + 7) << endl; for(int i = 0; i < k; i++) if(ans >> i & 1) cout << n[i] << endl; }