#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 13;

inline void boost () {
	ios_base::sync_with_stdio (0);
	cin.tie (0), cout.tie (0);
}
int n, c[N], q;
string s[N];

struct trie {
	int nxt[27], sum;
	trie () {
		memset (nxt, 0, sizeof nxt);
		sum = 0;
	}
} t[N];
int sz = 1;
int pos[N], dp[N];

void add (int i) {
	int v = 1;
	for (auto it : s[i]) {
		int to = it - 'a';
		if (!t[v].nxt[to])
			t[v].nxt[to] = ++ sz;
		v = t[v].nxt[to];
	}
	t[v].sum += c[i];
	pos[i] = v;
}
int timer, tin[N], tout[N], pr[25][N];

void dfs (int v = 1, int par = -1) {
	tin[v] = ++ timer;
	dp[v] += t[v].sum;
	pr[0][v] = par;
	for (int i = 1;i <= 23;i ++)
		pr[i][v] = pr[i - 1][pr[i - 1][v]];
	for (int to = 0;to < 26;to ++) {
		if (!t[v].nxt[to])
			continue;
		dfs (t[v].nxt[to], v);
	}
	tout[v] = ++ timer;
}
struct node {
	int val, add;
	node () {
		val = add = 0;
	}
};
vector < node > T;

void push (int v, int tl, int tr) {
	if (!T[v].add) return;
	T[v].val += (tr - tl + 1) * T[v].add;
	if (tl != tr) {
		T[v + v].add += T[v].add;
		T[v + v + 1].add += T[v].add;
	}
	T[v].add = 0;
}
void upd (int l, int r, int val, int v = 1, int tl = 1, int tr = timer) {
	push (v, tl, tr);
	if (tl > r || tr < l || l > r || tl > tr) return;
	if (l <= tl && tr <= r) {
		T[v].add += val;
		push (v, tl, tr);
		return;
	}
	int tm = (tl + tr) >> 1;
	upd (l, r, val, v + v, tl, tm);
	upd (l, r, val, v + v + 1, tm + 1, tr);
	T[v].val = T[v + v].val + T[v + v + 1].val;
}
int get (int l, int r, int v = 1, int tl = 1, int tr = timer) {
	push (v, tl, tr);
	if (tl > r || tr < l || l > r || tl > tr) return 0;
	if (l <= tl && tr <= r) return T[v].val;
	int tm = (tl + tr) >> 1;
	return get (l, r, v + v, tl, tm) + get (l, r, v + v + 1, tm + 1, tr);
}
int parent (int v, int k) {
	for (int i = 23;i >= 0;i --)
		if (((1 << i) & k))
			v = pr[i][v];
	return pr[0][v];
}

int main () {
	boost ();
	cin >> n >> q;
	for (int i = 1;i <= n;i ++) cin >> s[i] >> c[i];
	for (int i = 1;i <= n;i ++) add (i);
	dfs ();
	T.resize (4 * n + 123);
	while (q --) {
		char tp;
		cin >> tp;
		if (tp == '?') {
			int x, k;
			cin >> x >> k;
			int vk = parent (x, k - 1);
			cout << dp[pos[x]] + get (tin[pos[x]], tin[pos[x]]) - (dp[vk] + get (tin[vk], tin[vk])) << endl;
		} else {
			int x, val;
			cin >> x >> val;
			upd (tin[pos[x]], tout[pos[x]], val);
		}
	}

return 0;
}



























































//made up by Dalen