#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e5 + 10;
int n, k, c, minc = INT_MAX, idx = 0, b[N];
struct node {
	int w, id, rnk = 0;
	bool operator< (const node &x) const {
		return x.w > w;
	}
} a[N];
unordered_map<string, priority_queue<node>> mp;

inline int read() {
	int x = 0, f = 1; char c = getchar();
	while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x * f;
}

signed main() {
	n = read(), k = read();
	for (int i = 1; i <= k; i++) c = read(), minc = min(minc, c);
	for (int i = 1; i <= n; i++) {
		a[i].w = read(), a[i].id = i;
		string s; char c = getchar();
		while (c < 'A' || c > 'Z') c = getchar();
		while (c >= 'A' && c <= 'Z') s += c, c = getchar();
		mp[s].push(a[i]);
	}
	for (auto& [x, q] : mp) {
		int num = 0;
		while (!q.empty()) {
			node cur = q.top(); q.pop();
			a[cur.id].rnk = ++num;
			if (num <= minc) b[++idx] = a[cur.id].w;
		}
	}
	sort(b + 1, b + idx + 1, greater<int>());
	for (int i = 1; i <= idx; i++) cout << b[i] << ' '; cout << endl;
	for (int i = 1; i <= n; i++) {
		int l = 1, r = idx + 1;
		while (l < r) {
			int mid = l + r >> 1;
			if (b[mid] > a[i].w) l = mid + 1;
			else r = mid;
		}
		if (a[i].rnk <= minc) printf("%d\n", l);
		else printf("%d\n", l - 1);
	}
	return 0;
}