/*
    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;
    }