/*
This is code of SuperJ6 for Codeforces.
Don't copy my code during f*kin' contests.

2.71828182845904523536
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<int, int>
#define f first
#define s second

const int mxn = 300001, k = 26;
int n, m, q;
string s;
int a[mxn], b[mxn], f[mxn], lk[mxn];
int tr[mxn][k];
multiset<int> ss[mxn];
queue<int> qq;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> q;
	
	for(int i = 0; i < n; i++){
		cin >> s;
		int p = 0;
		for(char &c : s){
			if(!tr[p][c -= 'a']) tr[p][c] = ++m;
			p = tr[p][c];
		}
		ss[a[i] = p].insert(0);
	}
	
	qq.push(0);
	while(!qq.empty()){
		int c = qq.front(), x = lk[c];
		qq.pop();
		f[c] = ss[x].empty() ? f[x] : x;
		for(int i = 0; i < k; i++){
			int &v = tr[c][i], y = !!c * tr[x][i];
			if(v) lk[v] = y, qq.push(v);
			else v = y;
		}
	}
	
	while(q--){
		int t;
		cin >> t;
		if(!~-t){
			int x, y;
			cin >> x >> y;
			x--;
			ss[a[x]].erase(ss[a[x]].find(b[x]));
			ss[a[x]].insert(b[x] = y);
		}else{
			cin >> s;
			int p = 0, ret = -1;
			for(char &c : s){
				p = tr[p][c -= 'a'];
				for(int i = p; i; i = f[i]){
					if(!ss[i].empty()) ret = max(ret, *ss[i].rbegin());
				}
			}
			cout << ret << endl;
		}
	}

	return 0;
}