#temp

from collections import defaultdict

# 读取输入
n, k = map(int, input().split())
c = list(map(int, input().split()))

# 存储队伍信息 (综合实力, 大学缩写)
teams = []
for i in range(n):
    w, s = input().split()
    w = int(w)
    teams.append((w, s, i))  # 记录队伍实力，大学缩写，和原始索引

# 按综合实力从高到低排序
teams.sort(reverse=True, key=lambda x: x[0])

# 每所大学只能派出有限队伍，我们用字典来存储各个大学在每个区域赛的限制情况
university_limits = defaultdict(lambda: [0] * k)

# 结果列表
result = [0] * n

# 对于每支队伍，从实力最强到最弱开始分配区域赛
for w, university, original_index in teams:
    min_rank = 0
    total_capacity = 0
    
    # 计算所有比赛可以选择的总容量
    for i in range(k):
        available_slots = c[i] - university_limits[university][i]
        total_capacity += available_slots
        min_rank += available_slots

    # 记录该队伍的最小可能排名
    result[original_index] = n - total_capacity + 1

    # 分配队伍到比赛中（最坏情况下假设这个队伍加入最大的比赛容量中）
    for i in range(k):
        if university_limits[university][i] < c[i]:
            university_limits[university][i] += 1
            break

# 输出结果
for rank in result:
    print(rank)