#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> c(k);
    for (int i = 0; i < k; i++) {
        cin >> c[i];
    }
    sort(c.begin(), c.end());

    vector<int> a(n);
    vector<string> b(n);
    map<string, vector<int>> mp;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        mp[b[i]].push_back(a[i]);
    }

    for (auto& entry : mp) {
        sort(entry.second.begin(), entry.second.end());
    }

    for (int i = 0; i < n; i++) {
        int ans = 1;
        auto it = mp.find(b[i]);
        
        if (it != mp.end()) {
            // Same category
            for (int j = 1; j <= k; j++) {
                if (a[i] < it->second[it->second.size() - j]) {
                    ans += j;
                    break;
                }
            }
        } else {
            // Different category
            for (int j = 1; j <= k; j++) {
                for (auto& pair : mp) {
                    if (pair.first != b[i] && a[i] < pair.second[pair.second.size() - j]) {
                        ans += j;
                        break;
                    }
                }
            }
        }
        cout << ans << endl;
    }

    return 0;
}