#include using namespace std; #define REP(i,a,n) for(int i=(a); i<(int)(n); i++) #define rep(i,n) REP(i,0,n) #define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it) #define ALLOF(c) (c).begin(), (c).end() typedef long long ll; typedef unsigned long long ull; #define MOD 1000000007 int H, W, K, P; int x[20]; int y[20]; string name[20]; int main(){ cin >> H >> W >> K >> P; rep(i,K){ cin >> x[i] >> y[i] >> name[i]; } double mx = 0; ll mx_mod = 0; ll mx_S = 0; for(ll S=0; S<(1<> f(H+1, vector(W+1, 0)); vector> dp(H+1, vector(W+1, 0)); vector> dp2(H+1, vector(W+1, 0)); rep(i,K){ if((S>>i)&1){ cnt++; }else{ f[x[i]][y[i]] = -1; } } if(cnt>P) continue; dp[0][0] = 1; rep(i,H+1){ rep(j,W+1){ if(i==0 && j==0) continue; if(f[i][j] == -1) continue; if(i-1>=0){ dp[i][j] += dp[i-1][j]; dp2[i][j] += dp2[i-1][j]; } dp[i][j] %= MOD; if(j-1>=0){ dp[i][j] += dp[i][j-1]; dp2[i][j] += dp2[i][j-1]; } dp[i][j] %= MOD; } } if(mx < dp2[H][W]){ mx = dp2[H][W]; mx_mod = dp[H][W]; mx_S = S; } } cout << mx_mod << endl; rep(i,K){ if((mx_S>>i)&1){ cout << name[i] << endl; } } return 0; }