def solve(): dp = [[0]*w for _ in range(h)] dp[0][0] = 1 for i in range(h): for j in range(w): if i==0==j or b[i][j]==0: continue if i: dp[i][j] += dp[i-1][j] if j: dp[i][j] += dp[i][j-1] return dp[-1][-1] h,w,k,p = map(int,input().split()) h += 1; w += 1 name = [] pos = [] for _ in range(k): x,y,n = input().split() name.append(n) pos.append((int(x),int(y))) b = [[1]*w for _ in range(h)] ans = val = 0 for mask in range(1<<k): c = 0 for i in range(k): x,y = pos[i] b[x][y] = mask>>i&1 c += mask>>i&1 if c > p: continue v = solve() if val < v: ans = mask val = v print(val) for i in range(k): if ans>>i&1: print(name[i])