#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+100,fix=26;
int nxt[maxn][fix],cnt=2,link[maxn],val[maxn],top[maxn];
multiset<int> vals[maxn];
void build()
{
    queue<int> q;
    q.push(1);
    fill(nxt[0],nxt[0]+fix,1);
    while(!q.empty())
    {
        int s=q.front();
        q.pop();
        top[s]=val[link[s]]>=0?link[s]:top[link[s]];
        for(int j=0;j<fix;j++)
        {
            if(nxt[s][j]==0)
            nxt[s][j]=nxt[link[s]][j];
            else
            {
                link[nxt[s][j]]=nxt[link[s]][j];
                q.push(nxt[s][j]);
            }
        }
    }
}
int main()
{
    memset(val,-1,sizeof(val));
    int n,q;
    cin>>n>>q;
    vector<int> e(n);
    val[1]=0;
    for(int i=0;i<n;i++)
    {
        string s;
        cin>>s;
        int p=1;
        for(auto c:s)
        {
            if(nxt[p][c-'a']==0)
            nxt[p][c-'a']=cnt++;
            p=nxt[p][c-'a'];
        }
        e[i]=p;
        vals[p].insert(0);
        val[p]=0;
    }
    build();
    vector<int> v(n);
    while(q--)
    {
        int type;
        cin>>type;
        if(type==1)
        {
            int i,x;
            cin>>i>>x;
            --i;
            int p=e[i];
            vals[p].erase(vals[p].find(v[i]));
            v[i]=x;
            vals[p].insert(x);
            val[p]=*vals[p].rbegin();
        }
        else
        {
            string s;
            cin>>s;
            int p=1,res=-1;
            for(auto c:s)
            {
                p=nxt[p][c-'a'];
                for(int q=p;q!=1;q=top[q])
                if(val[q]>res)
                res=val[q];
            }
             cout<<res<<'\n';
        }
    }
   return 0;
}