MOD = 10**9 + 7

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

max_count = 0
best_mask = None

for mask in range(0, 1 << K):
    # Check if the number of set bits is <= P
    bit_count = bin(mask).count('1')
    if bit_count > P:
        continue
    
    # Generate blocked cells (friends not in this mask)
    blocked = set()
    for idx in range(K):
        if not (mask & (1 << idx)):
            xf, yf, _ = friends[idx]
            blocked.add((xf, yf))
    
    # Initialize DP table
    dp = [[0] * (W + 1) for _ in range(H + 1)]
    dp[0][0] = 1  # Starting point
    
    for i in range(H + 1):
        for j in range(W + 1):
            if i == 0 and j == 0:
                continue  # Already initialized
            if (i, j) in blocked:
                dp[i][j] = 0
                continue
            top = dp[i-1][j] if i > 0 else 0
            left = dp[i][j-1] if j > 0 else 0
            dp[i][j] = (top + left) % MOD
    
    current_count = dp[H][W]
    if current_count > max_count:
        max_count = current_count
        best_mask = mask
    elif current_count == max_count and current_count != 0:
        # According to problem statement, there is a unique maximum
        # So this case won't occur for valid test cases
        pass

if max_count == 0 or best_mask is None:
    print(0)
else:
    print(max_count % MOD)
    # Collect the names in the order of input
    selected_names = [friends[idx][2] for idx in range(K) if (best_mask & (1 << idx))]
    for name in selected_names:
        print(name)