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

struct node {
	int nxt[26];
	int pr, from = -1;
	int to[26];
	int ch, pm = -1;
	node() {
		memset(to, -1, sizeof to);
	}
};

const int N = 3e5 + 3;
node Tree[N];
int cnt = 0;
multiset<int> m[N];

int add(string& s) {
	int r = 0;
	for (auto&x : s) {
		if (!Tree[r].nxt[x - 'a']) {
			Tree[r].nxt[x - 'a'] = ++cnt;
			Tree[cnt].pr = r;
			Tree[cnt].ch = x - 'a';
		}
		r = Tree[r].nxt[x - 'a'];
	}
	return r;
}

int go(int v, int c) ;

int link(int v) {
	if (!v) return 0;
	if (Tree[v].from == -1) {
		if (!Tree[v].pr) return Tree[v].from = 0;
		int c = Tree[v].ch;
		Tree[v].from = go(link(Tree[v].pr), c);
	}
	return Tree[v].from;
}

int pure_memory(int v) {
	if (!v) return 0;
	if (Tree[v].pm == -1) Tree[v].pm = link(v);
	if (m[Tree[v].pm].empty()) {
		Tree[v].pm = pure_memory(Tree[v].pm);
	}
	return Tree[v].pm;
}

int go(int v, int c) {
	if (Tree[v].to[c] == -1) {
		if (Tree[v].nxt[c] || !v) Tree[v].to[c] = Tree[v].nxt[c];
		else Tree[v].to[c] = go(link(v), c);
	}
	return Tree[v].to[c];
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	vector<int> pos(n);
	vector<int> a(n, 0);
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		pos[i] = add(s);
		m[pos[i]].insert(0);
	}
	while (q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int id, val;
			cin >> id >> val;
			--id;
			m[pos[id]].erase(m[pos[id]].find(a[id]));
			a[id] = val;
			m[pos[id]].insert(a[id]);
		}
		else {
			string s;
			cin >> s;
			int r = 0;
			int ans = -1;
			for (auto&x : s) {
				r = go(r, x - 'a');
				int now = r;
				while (now) {
					if (!m[now].empty()) ans = max(ans, *prev(m[now].end()));
					now = pure_memory(now);
				}
			}
			cout << ans << "\n";
		}
	}
}