#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int trie[303030][26],belong[303030],fail[303030],tot=0,rt=0,orw[303030];
multiset<int> w[303030];
int n,m;
char s[303030];
int clrsta[303030],top=0;int vis[303030];
inline void build(){
    queue<int> q;
    for(int i=0;i<26;++i){
        if(trie[rt][i]){
            fail[trie[rt][i]]=rt;
            q.push(trie[rt][i]);
        }
    }
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=0;i<26;++i){
            if(trie[u][i]){
                fail[trie[u][i]]=trie[fail[u]][i];
                q.push(trie[u][i]);
            }else{
                trie[u][i]=trie[fail[u]][i];
            }
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1,len,cur;i<=n;++i){
        scanf("%s",s+1);
        len=strlen(s+1);
        cur=rt;
        for(int j=1;j<=len;++j){
            if(!trie[cur][s[j]-'a'])trie[cur][s[j]-'a']=++tot;
            cur=trie[cur][s[j]-'a'];
        }
        belong[i]=cur;
        w[cur].insert(0);
    }
    build();
    for(int i=1,op;i<=m;++i){
        scanf("%d",&op);
        if(op==1){
            int i,x;
            scanf("%d%d",&i,&x);
            w[belong[i]].erase(w[belong[i]].find(-orw[i]));
            w[belong[i]].insert(-x);
            orw[i]=x;
        }else{
            scanf("%s",s+1);
            int len=strlen(s+1);
            int cur=rt,cpcur;
            int ans=-1;
            for(int j=1;j<=len;++j){
                cpcur=cur=trie[cur][s[j]-'a'];
                while(!vis[cpcur]){
                    if(w[cpcur].size())ans=max(ans,-*(w[cpcur].begin()));
                    vis[cpcur]=1;
                    clrsta[++top]=cpcur;
                    cpcur=fail[cpcur];
                }
            }
            printf("%d\n",ans);
            while(top)vis[clrsta[top--]]=0;
        }
    }
}