import sys
from itertools import combinations

MOD = 10**9 + 7

def main():
    H, W, K, P = map(int, sys.stdin.readline().split())
    friends = []
    for _ in range(K):
        x, y, name = sys.stdin.readline().split()
        x = int(x)
        y = int(y)
        friends.append((x, y, name))
    
    max_count = -1
    best_S = None
    
    # 当P=0时，支付为空，直接计算障碍物为所有朋友
    if P == 0:
        obstacles = set()
        for x, y, _ in friends:
            obstacles.add((x, y))
        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
                if (i, j) in obstacles:
                    dp[i][j] = 0
                else:
                    total = 0
                    if i > 0:
                        total += dp[i-1][j]
                    if j > 0:
                        total += dp[i][j-1]
                    dp[i][j] = total % MOD
        current = dp[H][W]
        if current == 0:
            print(0)
            return
        else:
            print(current % MOD)
            print()
            return
    
    for S in combinations(range(K), P):
        obstacles = set()
        for i in range(K):
            if i not in S:
                x, y, _ = friends[i]
                obstacles.add((x, y))
        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
                if (i, j) in obstacles:
                    dp[i][j] = 0
                else:
                    total = 0
                    if i > 0:
                        total += dp[i-1][j]
                    if j > 0:
                        total += dp[i][j-1]
                    dp[i][j] = total % MOD
        current = dp[H][W]
        if current > max_count:
            max_count = current
            best_S = S
    
    if max_count == 0:
        print(0)
        return
    
    print(max_count % MOD)
    if best_S is not None:
        sorted_S = sorted(best_S)
        for idx in sorted_S:
            print(friends[idx][2])
    print()

if __name__ == "__main__":
    main()