from bisect import bisect
d={}
f = open(r"C:\Users\29784\Documents\WeChat Files\wxid_sq65x06x9lok22\FileStorage\File\2024-09\2.in")
ss=f.readlines()
a,_ =map(int,ss[0].split())
n=min(map(int,ss[1].split()))
an=[]
def che(c,x):
    # l,r=0,len(c)-1
    # mid=(l+r)//2
    # if c[-1]>=x:
    #     return len(c)-1
    # while 1:
    #     if l>=r-1: break
    #     if x<=c[mid]:
    #         l=mid
    #     else:
    #         r=mid
    #     mid = (l + r) // 2
    # return l
    l = 0
    r = len(c) - 1
    # print(x)
    while l < r:
        mid = (l + r) // 2
        if c[mid] >= x :
            r = mid
        else :
            l = mid + 1

    return l


for iso in range(a):
    a1,a2=ss[2+iso].split()
    a1=int(a1)
    an.append(a1)
    if a2 in d:
        d[a2].append(a1)
    else:d[a2]=[a1]
c=[]
for i in d.values():
    k=i.copy()
    k.sort()
    c+=k[len(i)-n:] if len(i)-n>=0 else k[:]

c.sort()
# c=c[::-1]
# print(c)
m = len(c)
su=0


for i in an:
    k=  m - che(c,i)
    print(k)