#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 2e18;

int get(vector<int>&v,int x){
    int n = v.size();
    int l = 0,r = n;
    while((l <= r) && (l < n)){
        int mid = (l + r) >> 1;
        if(v[mid] >= x){
            l = mid + 1;
        }
        else{
            r = mid - 1;
        }
    }
    return l;
}

void solve(){
    int n = 0,k = 0;
    cin >> n >> k;
    int mn = INF;
    for(int i = 0;i < k;i++){
        int x = 0;
        cin >> x;
        mn = min(mn,x);
    }
    map<string,vector<int>>v;
    map<int,int>mp;
    for(int i = 0;i < n;i++){
        int val = 0;
        string s;
        cin >> val >> s;
        v[s].push_back(val);
        mp[val] = i;
    }
    vector<int>vec;
    for(auto& it : v){
        sort(it.second.begin(),it.second.end(),greater<int>());
    }
    for(auto& it : v){
        for(int i = 0;i < min((int)it.second.size(),mn);i++){
            vec.push_back(it.second[i]);
        }
    }
    vector<int>ans(n);
    for(auto& it : v){
        for(int i = 0;i < (int)it.second.size();i++){
            if(i < mn){
                ans[mp[it.second[i]]] = get(vec,it.second[i]);
            }
            else{
                ans[mp[it.second[i]]] = get(vec,it.second[i]);
            }
        }
    }
    for(int i = 0;i < n;i++){
        cout << ans[i] << endl;
    }
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    solve();
    return 0;
}