MOD = 10**9 + 7

H, W, K, P = map(int, input().split())
friends = []
for _ in range(K):
    x, y, name = input().split()
    x = int(x)
    y = int(y)
    friends.append((x, y, name))

# Precompute the grid: each cell has the friend index or -1
grid = [[-1 for _ in range(W + 1)] for __ in range(H + 1)]
for idx in range(K):
    x, y, name = friends[idx]
    grid[x][y] = idx

max_paths = 0
best_mask = None

for mask in range(0, 1 << K):
    s = bin(mask).count('1')
    if s > P:
        continue
    
    # Initialize DP table
    dp = [[0] * (W + 1) for _ in range(H + 1)]
    dp[0][0] = 1
    
    for i in range(H + 1):
        for j in range(W + 1):
            if i == 0 and j == 0:
                continue
            
            # Check if the cell is blocked
            if grid[i][j] != -1:
                friend_idx = grid[i][j]
                if (mask & (1 << friend_idx)) == 0:
                    dp[i][j] = 0
                    continue
            
            # Calculate the number of paths
            sum_val = 0
            if i > 0:
                sum_val += dp[i-1][j]
            if j > 0:
                sum_val += dp[i][j-1]
            dp[i][j] = sum_val % MOD
    
    current = dp[H][W]
    if current > max_paths:
        max_paths = current
        best_mask = mask

if max_paths == 0:
    print(0)
else:
    print(max_paths % MOD)
    # Collect the names in the order of their occurrence in the input
    output = []
    for idx in range(K):
        if (best_mask & (1 << idx)) != 0:
            output.append(friends[idx][2])
    for name in output:
        print(name)
    print()