萌新袜子求条虚树

#include <bits/stdc++.h>
#define X first
#define Y second
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define per(i, a, b) for (int i = a; i >= b; i--)
#define E(i, u) for (int i = h[u], v = e[h[u]].to; ~i; i = e[i].nxt, v = e[i].to)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mid (l + r >> 1)
using namespace std;
typedef long long int ll;
using ull = unsigned long long int; using ld = double;
using pii = pair<int, int>;
template<typename T> using pq = priority_queue<T>; using pli = pair<ll, int>;
template<typename T> using vec = vector<T>;
constexpr int maxn = 5e5 + 10, K = 6e5 + 10, B = 537, bs = 197, maxv = 1e9 + 10, mod = 998244353, V = 1e3; constexpr int inf = 1.05e9;
inline ll ksm(ll a, int b = mod - 2) { ll ls = 1; while (b) (b & 1) && (ls = ls * a % mod), a = a * a % mod, b >>= 1; return ls; }
inline ll dksm(ll a, int b, int p) { ll ls = 1; while (b) (b & 1) && (ls = ls * a % p), a = a * a % p, b >>= 1; return ls; }
int gcd(int n, int m) { return !m ? n : gcd(m, n % m); }
int q[maxn], hd = 1, tl, T[maxn][5], fa[maxn], tot, rt[maxn], n, m, cnt; vec<int> g[maxn], tv[maxn];
struct Node { int l, r, v; } t[maxn * 18];
#define ls(x) (t[x].l)
#define rs(x) (t[x].r)
#define w(x) (t[x].v)
void mdf(int l, int r, int v, int p, int& x) {
	t[x = ++cnt] = t[p]; ++w(x); if (l == r) return;
	v <= mid ? mdf(l, mid, v, ls(p), ls(x)) : mdf(mid + 1, r, v, rs(p), rs(x));
}
int qry(int l, int r, int k, int p, int x) {
	if (!x) return 0;
	if (k <= l) return w(x) - w(p); int sum = 0;
	if (k <= mid) sum += qry(l, mid, k, ls(p), ls(x));
	sum += qry(mid + 1, r, k, rs(p), rs(x));
	return sum;
}
void ins(char* S, int k) {
	int u = 0, p = strlen(S + 1);
	rep(i, 1, p) {
		int d = S[i] - 'a';
		if (!T[u][d]) T[u][d] = ++tot;
		u = T[u][d];
	}
	tv[u].pb(k);
}
void bd() {
	rep(i, 0, 3) if (T[0][i]) q[++tl] = T[0][i];
	while (hd <= tl) {
		int u = q[hd++];
		g[fa[u]].pb(u);
		rep(i, 0, 3) {
			int v = T[u][i];
			if (v) fa[v] = T[fa[u]][i], q[++tl] = v;
			else T[u][i] = T[fa[u]][i];
		}
	}
}
char ac[maxn]; int dfn[maxn], dct;
int st[20][maxn], lg[maxn], sz[maxn];
inline int ck(int x, int y) { return dfn[x] < dfn[y] ? x : y; }
inline int lca(int u, int v) {
	if (u == v) return u;
	else if ((u = dfn[u]) > (v = dfn[v])) swap(u, v);
	int g = lg[v - u++];
	return ck(st[g][u], st[g][v - (1 << g) + 1]);
}
void init(int u) {
	st[0][dfn[u] = ++dct] = fa[u]; rt[u] = rt[fa[u]];
	for (int x : tv[u]) mdf(0, 1000, x, rt[u], rt[u]);
	for (int v : g[u]) init(v);
}
vec<int> vr_g[maxn];
void dfs(int u) { for (int v : vr_g[u]) dfs(v), sz[u] += sz[v]; }
inline int ckmid(int u, int md) {
	int ct = 0; 
	for (int v : vr_g[u]) {
		ct += ckmid(v, md);
		if ((md + sz[v] - 1) / sz[v] <= 1000) ct += qry(0, 1000, (md + sz[v] - 1) / sz[v], rt[u], rt[v]);
	}
	return ct;
}
int solve(int K) {
	int u = 0, len = strlen(ac + 1); vec<int> a, h; a.pb(0), h.pb(0);
	rep(i, 1, len) u = T[u][ac[i] - 'a'], ++sz[u], a.pb(u), h.pb(u);
	auto cmp = [&](int i, int j) { return dfn[i] < dfn[j]; };
	sort(h.begin(), h.end(), cmp); 
	rep(i, 1, (int)h.size() - 1) a.pb(lca(h[i - 1], h[i]));
	sort(a.begin(), a.end(), cmp); a.erase(unique(a.begin(), a.end()), a.end());
	rep(i, 1, (int)a.size() - 1) vr_g[lca(a[i - 1], a[i])].pb(a[i]); //, cout << lca(a[i - 1], a[i]) << " " << a[i] << "\n";
	int l = 1, r = 5e8 + 100, ans = 0; dfs(0);
	while (l <= r) {
		ll M = l + r >> 1;
		if (ckmid(0, M) >= K) l = M + 1, ans = M;
		else r = M - 1;
	}
	for(int x : a) sz[x] = 0, vr_g[x].clear(); a.clear(), h.clear(); 
	return ans;
}
int main() {
	scanf("%d%d", &n, &m); int k;
	rep(i, 2, maxn - 1) lg[i] = lg[i >> 1] + 1;
	rep(i, 1, n) {
		scanf("%s%d", ac + 1, &k);
		ins(ac, k); 
	}
	bd(); init(0);
	rep(i, 1, lg[tot]) rep(j, 1, tot - (1 << i) + 1) st[i][j] = ck(st[i - 1][j], st[i - 1][j + (1 << i - 1)]);
	rep(i, 1, m) {
		scanf("%s%d", ac + 1, &k);
		printf("%d\n", solve(k));
	}
	return 0;
}