MOD = 10**9 + 7

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    H = int(input[ptr]); ptr +=1
    W = int(input[ptr]); ptr +=1
    K = int(input[ptr]); ptr +=1
    P = int(input[ptr]); ptr +=1

    friends = []
    pos_map = {}

    for i in range(K):
        x = int(input[ptr]); ptr +=1
        y = int(input[ptr]); ptr +=1
        name = input[ptr]; ptr +=1
        friends.append( (x, y, name) )
        pos_map[(x, y)] = i

    max_count = 0
    best_mask = None

    for mask in range(0, 1 << K):
        count_bits = bin(mask).count('1')
        if count_bits > P:
            continue

        dp = [ [0] * (W + 1) for _ in range(H + 1) ]
        dp[0][0] = 1

        for x in range(H + 1):
            for y in range(W + 1):
                if x == 0 and y == 0:
                    continue

                if (x, y) in pos_map:
                    friend_idx = pos_map[(x, y)]
                    if not (mask & (1 << friend_idx)):
                        dp[x][y] = 0
                        continue

                total = 0
                if x > 0:
                    total += dp[x-1][y]
                if y > 0:
                    total += dp[x][y-1]
                dp[x][y] = total % MOD

        current_count = dp[H][W]
        if current_count > max_count:
            max_count = current_count
            best_mask = mask

    if max_count == 0:
        print(0)
    else:
        print(max_count % MOD)
        selected = []
        for i in range(K):
            if best_mask & (1 << i):
                selected.append(friends[i][2])
        for name in selected:
            print(name)

if __name__ == "__main__":
    main()