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

MOD = 10**9 + 7

max_count = 0
best_mask = 0

for mask in range(0, 1 << K):
    bits = bin(mask).count('1')
    if bits > P:
        continue
    
    previous_row = [0] * (W + 1)
    previous_row[0] = 1  # Starting point (0,0)
    
    for i in range(H + 1):
        current_row = [0] * (W + 1)
        for j in range(W + 1):
            if i == 0 and j == 0:
                current_row[j] = 1
                continue
            
            # Check if current cell is blocked
            fi = friend_index[i][j]
            if fi != -1 and not (mask & (1 << fi)):
                current_row[j] = 0
                continue
            
            total = 0
            if i > 0:
                total += previous_row[j]
            if j > 0:
                total += current_row[j - 1]
            current_row[j] = total % MOD
        
        previous_row = current_row
    
    current_count = previous_row[W]
    
    if current_count > max_count:
        max_count = current_count
        best_mask = mask
    elif current_count == max_count and mask < best_mask:
        best_mask = mask

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