#include<bits/stdc++.h>
using namespace std;
const int maxn=300005;
int ch[maxn][26],fail[maxn],cnt;
int top[maxn],n,m,tg[maxn];
int ep[maxn],v[maxn],val[maxn];
multiset<int>s[maxn];
int main(){
	ios::sync_with_stdio(0); 
	cin>>n>>m;
	memset(val,-1,sizeof val);
	for(int i=1;i<=n;i++){
		string str;
		cin>>str;
		int u=0;
		for(auto x:str){
			u=ch[u][x-'a']?ch[u][x-'a']:(ch[u][x-'a']=++cnt);
		}
		ep[i]=u;
		s[u].insert(0);
		val[u]=0;
		tg[u]=1;
	}
	queue<int>q;
	tg[0]=1;
	top[0]=0;
	for(int i=0;i<26;i++){
	    if(ch[0][i]){
	    	fail[ch[0][i]]=0;
	    	if(tg[fail[ch[0][i]]])
	    	top[ch[0][i]]=fail[ch[0][i]];
	    	else top[ch[0][i]]=top[fail[ch[0][i]]];
	    	q.push(ch[0][i]);
		}
	}
	while(q.size()){
		int x=q.front();
		q.pop();
		for(int i=0;i<26;i++){
			if(ch[x][i]){
		    	fail[ch[x][i]]=ch[fail[x]][i];
		    	if(tg[fail[ch[x][i]]])
		    	top[ch[x][i]]=fail[ch[x][i]];
		    	else top[ch[x][i]]=top[fail[ch[x][i]]];
		    	q.push(ch[x][i]);
			}
			else{
				ch[x][i]=ch[fail[x]][i];
			}
		}
	}
	while(m--){
		int op,i,x;string q;
		cin>>op;
		if(op==1){
			cin>>i>>x; 
			int u=ep[i];
			s[u].erase(s[u].find(v[i]));
			v[i]=x;
			s[u].insert(x);
			val[u]=*s[u].rbegin();
		}
		else{
			int ans=-1;
			cin>>q;
			int u=0;
			for(auto x:q){
				u=ch[u][x-'a'];
				for(int v=u;v;v=top[v])
				ans=max(ans,val[v]);
			}
			cout<<ans<<"\n";
		}
	}
	
	 
}