name_points = input().split()
n = int(input())

free_spots = name_points[-1]
free_spots = int(free_spots)

names = []
points = []
for i in range(n):
    child = input().split()
    names.append(child[0])
    points.append(child[-1])


points_lst = [int(i) for i in points]


child_dict = dict(zip(names, points))


names_approved_childs = []
counter = 0
replacement_key = ''
for key, value in child_dict.items():

    while counter < free_spots:
        max_points = max(child_dict, key=child_dict.get)
        names_approved_childs.append(max_points)
        child_dict[max_points] = replacement_key
        counter += 1




rest_of_them = []
for key in child_dict:
    if key in names_approved_childs:
        continue
    rest_of_them.append(key)


print(*names_approved_childs)

if len(rest_of_them) != 0:
    print(*rest_of_them)

else:
    print('n/a')