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

const int maxn = 3e5+5;
vector<array<int, 26>> go = {{}};
vector<int> suf, sup;
vector<multiset<int>> mxs = {{-1}};
bool term[maxn];
int n, q, nodes = 1, node[maxn], sus[maxn];
string s;

void insert(int id){
	int pos = 0;
	for(int i = 0; i<s.size(); i++) {
		char nxt = s[i] - 'a';
		if (!go[pos][nxt]) {
			go[pos][nxt] = nodes++;
			go.push_back({});
			mxs.push_back({-1});
		} 
		pos = go[pos][nxt];
	}
	term[pos] = true;
	mxs[pos].emplace(0);
	node[id] = pos;
}

void build(){
	sup.resize(nodes, 0);
	suf.resize(nodes, 0);
	queue<int> q;
	q.push(0);
	while(q.size()) {
		int u =	q.front();
		q.pop();
		sup[u] = term[suf[u]] ? suf[u] : sup[suf[u]];
		for(int i = 0; i<26; i++){
			if (go[u][i]) {
				suf[go[u][i]] = u ? go[suf[u]][i] : 0;
				q.push(go[u][i]);
			} else go[u][i] = u ? go[suf[u]][i] : 0;
		}
	}
}

void upd() {
	int id, x;
	cin >> id >> x;
	int v = node[id];
	mxs[v].erase(mxs[v].find(sus[id]));
	mxs[v].emplace(sus[id] = x);
}

void query() {
	cin >> s;
	int pos = 0, ans = -1;
	for(int i = 0; i<s.size(); i++) {
		pos = go[pos][s[i]-'a'];
		int v = pos;
		while(v > 0) ans = max(ans, *mxs[v].rbegin()), v = sup[v];
	}
	cout << ans << '\n';
}


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> q;
	for(int i = 0; i<n; i++){
		cin >> s;
		insert(i+1);
	}
	build();
	for(int i = 0; i<q; i++) {
		int t;
		cin >> t;
		if (t == 1) upd();
		else query();
	}
	return 0;
}