#include<bits/stdc++.h>
const int mod=1e9+7; 
using namespace std;
int n,m,id[300010];char c[300010];
int ch[300010][26],cn=1,dfn[300010],siz[300010],fail[300010];
vector<int>g[300010];
priority_queue<int>s[1200010],s2[1200010];queue<int>q;
void build(){
	for(int i=0;i<26;i++)if(!ch[1][i])ch[1][i]=1;else fail[ch[1][i]]=1,q.push(ch[1][i]);
	while(!q.empty()){
		int u=q.front();q.pop(),g[fail[u]].push_back(u);
		for(int i=0;i<26;i++)
			if(!ch[u][i])ch[u][i]=ch[fail[u]][i];
			else q.push(ch[u][i]),fail[ch[u][i]]=ch[fail[u]][i];
	}
}
void d1a1(int p,int l,int r,int x,int y,int a,int b){
	if(x<=l&&r<=y){s2[p].push(a);s[p].push(b);return;}
	if(r<x||l>y)return;
	int mid=(l+r)>>1;
	d1a1(p<<1,l,mid,x,y,a,b);d1a1(p<<1|1,mid+1,r,x,y,a,b); 
}
int ask(int x){
	int p=1,l=1,r=cn,ans=-1;
	while(1){
		while(!s2[p].empty()&&!s[p].empty()&&s2[p].top()==s[p].top())s2[p].pop(),s[p].pop();
		if(!s[p].empty())ans=max(ans,s[p].top());
		if(l==r)break;int mid=(l+r)>>1;
		if(x<=mid)r=mid,p<<=1;else l=mid+1,p=(p<<1)|1;
	}
	return ans;
}
void dfs(int x){
	dfn[x]=++dfn[0];siz[x]=1;
	for(int i=0,v;i<g[x].size();i++){
		v=g[x][i];dfs(v);
		siz[x]+=siz[v];
	}
}
int val[300010];
int main(){
	scanf("%d%d",&n,&m);
	for(int p=1;p<=n;p++){
		scanf("%s",c);int l=strlen(c),u=1;
		for(int i=0;i<l;i++){
			if(!ch[u][c[i]-'a'])ch[u][c[i]-'a']=++cn;
			u=ch[u][c[i]-'a'];
		}
		id[p]=u;
	}
	build();dfs(1);
	for(int i=1;i<=4*cn;i++)s[i].push(-1);
	for(int i=1;i<=n;i++)d1a1(1,1,cn,dfn[id[i]],dfn[id[i]]+siz[id[i]]-1,-1,0);
	while(m--){
		int type,x,y;scanf("%d",&type);
		if(type==1)scanf("%d%d",&x,&y),d1a1(1,1,cn,dfn[id[x]],dfn[id[x]]+siz[id[x]]-1,val[x],y),val[x]=y;
		else{
			scanf("%s",c);int l=strlen(c),u=1,ans=-1;
			for(int i=0;i<l;i++){
				u=ch[u][c[i]-'a'];
				ans=max(ans,ask(dfn[u]));
			}
			printf("%d\n",ans);
		}
	}
	return 0;
}