#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<cctype>
#include<stack>
#include<map>
#include<climits>
#include<set>
#include<iostream>
#define rint() read<int>()
#define rll() read<ll>()
#define rep(i,a,b) for(register int i=a;i<=b;++i)
#define rev(i,a,b) for(register int i=a;i>=b;--i)
#define gra(i,u) for(register int i=head[u];i;i=edge[i].nxt)
#define Clear(a) memset(a,0,sizeof(a))
using namespace std;
typedef long long ll;
inline int read()
{
	register int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')s=s*10+(ch-'0'),ch=getchar();
	return s*w;
}
const int INF=1e9;
const ll LLINF=1e18;
template<typename T>
inline T Min(T x,T y){return x<y?x:y;}
template<typename T>
inline T Max(T x,T y){return x>y?x:y;}
template<typename T>
inline void Swap(T&x,T&y){int t=x;x=y;y=t;return;}
const int MAXN(3e5+10);
int n,m,pos[MAXN],pool;
struct E{int to,nxt;};
E edge[MAXN];
int head[MAXN],tot;
int cntt;
inline void add_edge(int u,int v){edge[++tot].nxt=head[u];head[u]=tot;edge[tot].to=v;return;}
struct Segment_Tree
{
	int tree[MAXN*4];
	inline int lc(int p){return p<<1;}
	inline int rc(int p){return p<<1|1;}
	inline void init_(){memset(tree,-1,sizeof(tree));return;}
	inline void push_up(int u){tree[u]=Max(tree[lc(u)],tree[rc(u)]);return;}
	inline void update(int u,int l,int r,int p,int k)
	{
		if(l==p&&r==p){tree[u]=k;return;}
		int mid=(l+r)>>1;
		if(p<=mid) update(lc(u),l,mid,p,k);
		else update(rc(u),mid+1,r,p,k);
		push_up(u);
		return;
	}
	inline int query(int u,int l,int r,int ln,int rn)
	{
		int res(-1);
		if(ln<=l&&r<=rn) return tree[u];
		int mid=(l+r)>>1;
		if(ln<=mid) res=Max(res,query(lc(u),l,mid,ln,rn));
		if(rn>mid) res=Max(res,query(rc(u),mid+1,r,ln,rn));
		return res; 
	}
};
Segment_Tree seg;
struct Fuck_Tree
{
	int par[MAXN],son[MAXN],idx[MAXN],rk[MAXN],top[MAXN],dep[MAXN],siz[MAXN];
	inline void dfs1(int u,int fa)
	{
		siz[u]=1,dep[u]=dep[fa]+1,par[u]=fa;
		gra(i,u)
		{
			E e=edge[i];
			if(e.to==fa) continue;
			dfs1(e.to,u);
			siz[u]+=siz[e.to];
			if(siz[son[u]]<siz[e.to]) son[u]=e.to;
		}
		return;
	}
	inline void dfs2(int u,int topf)
	{
		top[u]=topf;
		idx[u]=++cntt;
		rk[cntt]=u;
		if(son[u]) dfs2(son[u],topf);
		gra(i,u)
		{
			E e=edge[i];
			if(e.to!=son[u]&&e.to!=par[u]) dfs2(e.to,e.to);
		}
		return;
	}
	inline void modify(int x,int k)
	{
		seg.update(1,1,cntt,idx[x],k);
		return;
	}
	inline int qmax(int x)
	{
		int fx=top[x],res(-1);
		while(fx!=0)
		{
			res=Max(res,seg.query(1,1,cntt,idx[fx],idx[x]));
			x=par[fx];
			fx=top[x];
		}
		res=Max(res,seg.query(1,1,cntt,idx[0],idx[x]));
		return res;
	}
};
Fuck_Tree fuck;
struct AC_Automaton
{
	int trie[MAXN][30],fail[MAXN];
	inline int idx(char c){return c-'a'+1;}
	inline void ins(vector<char>s,int id)
	{
		int len=s.size()-1,p(0);
		rep(i,0,len)
		{
			int c=idx(s[i]);
			if(!trie[p][c]) trie[p][c]=++pool;
			p=trie[p][c];
		}
		pos[id]=p;
		return;
	}
	inline void get_fail()
	{
		queue<int>q;
		rep(i,1,26)
		{
			int u=trie[0][i];
			if(u) fail[u]=0,q.push(u);
		}
		while(!q.empty())
		{
			int u=q.front();
			q.pop();
			int fa=fail[u];
			rep(i,1,26)
			{
				int v=trie[u][i];
				if(v) fail[v]=trie[fa][i],q.push(v);
				else trie[u][i]=trie[fa][i];
			}
		}
		rep(i,1,pool) add_edge(fail[i],i);
		return;
	}
	inline int query(vector<char>s)
	{
		int len=s.size()-1,p(0),ans(-1);
		rep(i,0,len)
		{
			int c=idx(s[i]);
			p=trie[p][c];
			ans=Max(ans,fuck.qmax(p));
		}
		return ans;
	}
};
AC_Automaton tree;
vector<char>s;
inline void get_char()
{
	char ch[MAXN];
	scanf("%s",ch);
	int len=strlen(ch);
	s.clear();
	rep(i,0,len-1) s.push_back(ch[i]);
	return;
}
int main()
{
	n=read(),m=read();
	rep(i,1,n)
	{
		get_char();
		tree.ins(s,i);
	}
	tree.get_fail();
	seg.init_();
	fuck.dfs1(0,0);
	fuck.dfs2(0,0);
	rep(i,1,n) fuck.modify(pos[i],0);
	while(m--)
	{
		int opt=read();
		if(opt==1)
		{
			int u=read(),k=read();
			fuck.modify(pos[u],k);
		}
		else
		{
			get_char();
			printf("%d\n",tree.query(s));
		}
	}
	return 0;
}