Problem: For the simplicity, let's say that the "Death Note" is a notebook that kills a person when their name is written in it.

It's easy to kill with it, but it's pretty hard to keep track of people you haven't killed and still plan to. You decided to make a "Death Database Management System" — a computer program that provides the easy access to the database of possible victims. Let me describe its specifications to you.

Let's define a victim entity: a victim has a name (not necessarily unique) that consists only of lowercase Latin letters and an integer suspicion value.

At the start of the program the user enters a list of n victim names into a database, each suspicion value is set to 0.

Then the user makes queries of two types: 

  * 1~i~x — set the suspicion value of the i-th victim to x; 
  * 2~q — given a string q find the maximum suspicion value of a victim whose name is a contiguous substring of q. 



Just to remind you, this program doesn't kill people, it only helps to search for the names to write down in an actual notebook. Thus, the list of the victims in the database doesn't change throughout the queries.

What are you waiting for? Write that program now!

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 3 ⋅ 10^5) — the number of victims and the number of queries, respectively.

Each of the next n lines contains a single string s_i — the name of the i-th victim. Each name consists only of lowercase Latin letters.

Each of the next m lines contains a query of one of two types: 

  * 1~i~x (1 ≤ i ≤ n, 0 ≤ x ≤ 10^9) — change the suspicion value of the i-th victim to x; 
  * 2~q — given a string q consisting only of lowercase Latin letters find the maximum suspicion value of a victim whose name is a contiguous substring of q. 



There is at least one query of the second type. The total length of the strings s_i doesn't exceed 3 ⋅ 10^5. The total length of the strings q doesn't exceed 3 ⋅ 10^5. 

Output

For each query of the second type print an integer value. If there is no victim name that is a contiguous substring of q, then print -1. Otherwise, print the maximum suspicion value of a victim whose name is a contiguous substring of q.

Examples

Input


5 8
kurou
takuo
takeshi
naomi
shingo
2 nakiraomi
2 abanaomicaba
1 3 943
2 takuotakeshishingo
1 5 135832
2 shingotakeshi
1 5 0
2 shingotakeshi


Output


-1
0
943
135832
943


Input


6 15
a
ab
ba
b
a
ba
2 aa
1 4 4
2 bbb
1 2 1
1 2 18
2 b
2 c
1 6 10
2 aba
2 abbbba
1 2 12
2 bbaaab
1 1 11
1 5 5
2 baa


Output


0
4
4
-1
18
18
12
11

Solution (in JAVA):

Solution:
import java.lang.reflect.Array;
import java.util.*;
import java.io.*;
import java.text.*;

public class Main{
    //SOLUTION BEGIN
    //Into the Hardware Mode
    int[][] g;
    int[] sub, de, par;
    int[] t;boolean[] lazy;int m = 1, B = 20;
    int chainNo = 0, pos = 0, chainHead[], chainInd[], treePos[], chainPos[], hc[];
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni(), Q = ni();
        AhoCorasick aho = new AhoCorasick(26, (int)1e6);
        int[] index = new int[N];
        for(int i = 0; i< N; i++)index[i] = aho.addString(i, n().toCharArray());
        aho.buildSuffixLinks();
        int n = aho.ID;
        MyTreeSet<Integer>[] valueSet = new MyTreeSet[n];
        for(int i = 0; i< N; i++){
            if(valueSet[index[i]] == null)valueSet[index[i]] = new MyTreeSet<>();
            valueSet[index[i]].add(0);
        }

        int[][] e = aho.slt();
        int[] from = new int[e.length], to = new int[e.length];
        for(int i = 0; i< e.length; i++){
            from[i] = e[i][0];
            to[i] = e[i][1];
        }
        g = make(n, e.length, from, to, false);
        int root = aho.sentinal;

        sub = new int[n]; de = new int[n];par = new int[n];
        Arrays.fill(par, -1);

        dfs1(g, par, sub, de, root);
        chainHead = new int[n];
        Arrays.fill(chainHead, -1);
        treePos = new int[n];

        Arrays.fill(chainHead, -1);
        hld(root);
        SegmentTree segtree = new SegmentTree(n);
        for(int i = 0; i< N; i++)segtree.update(treePos[index[i]], 0);
        int[] A = new int[N];
        while (Q-->0){
            if(ni() == 1){
                int ind = ni()-1, val = ni();

                int maxVal = upd(valueSet, index[ind], A[ind], val);
                A[ind] = val;
                segtree.update(treePos[index[ind]], maxVal);
            }else{
                char[] text = n().toCharArray();
                int state = aho.root;
                long ans = -1;
                for(char i:text){
                    state = aho.move(state, i);
                    ans = Math.max(ans, queryUp(segtree, state));
                }
                pn(ans);
            }
        }
    }
    int upd(MyTreeSet<Integer>[] valueSet, int ind, int old, int newVal){
        valueSet[ind].remove(old);
        valueSet[ind].add(newVal);
        return valueSet[ind].last();
    }
    class MyTreeSet<T> implements Iterable<T>{
        private int size;
        private TreeMap<T, Integer> map;
        public MyTreeSet(){
            size = 0;
            map = new TreeMap<>();
        }
        public int size(){return size;}
        public int dsize(){return map.size();}
        public boolean isEmpty(){return size==0;}
        public void add(T t){
            size++;
            map.put(t, map.getOrDefault(t, 0)+1);
        }
        public boolean remove(T t){
            if(!map.containsKey(t))return false;
            size--;
            int c = map.get(t);
            if(c==1)map.remove(t);
            else map.put(t, c-1);
            return true;
        }
        public int freq(T t){return map.getOrDefault(t, 0);}
        public boolean contains(T t){return map.getOrDefault(t,0)>0;}
        public T ceiling(T t){return map.ceilingKey(t);}
        public T floor(T t){return map.floorKey(t);}
        public T first(){return map.firstKey();}
        public T last(){return map.lastKey();}
        public Iterator<T> iterator() {
            return new MyTreeSetIterator<>(this);
        }
        class MyTreeSetIterator<T> implements Iterator<T>{
            TreeMap<T, Integer> mp;
            T element = null;
            int cur = 0, freq = 0;
            MyTreeSetIterator(MyTreeSet<T> obj){
                this.mp = obj.map;
                if(!this.mp.isEmpty()){
                    element = mp.firstKey();
                    freq = mp.firstEntry().getValue();
                }
            }
            public boolean hasNext(){
                return element != null;
            }
            public T next(){
                T ret = element;
                cur++;
                if(cur == freq){
                    Map.Entry<T, Integer> e = mp.higherEntry(element);
                    if(e == null){
                        element = null;
                        freq = 0;
                    }else{
                        element = e.getKey();
                        freq = e.getValue();
                        cur = 0;
                    }
                }
                return ret;
            }
        }
    }
    long queryUp(SegmentTree segtree, int node){
        long ans = -1;
        while(node != -1){
            int ch = chainHead[node];
            ans = Math.max(ans, segtree.query(treePos[ch], treePos[node]));
            node = par[ch];
        }
        return ans;
    }
    void hld(int u){
        if(chainHead[u]==-1)chainHead[u] = u;
        treePos[u] = pos++;
        int ch = -1;
        for(int v:g[u]){
            if(v==par[u])continue;
            if(ch==-1 || sub[ch]<sub[v])ch = v;
        }
        if(ch>=0){
            chainHead[ch] = chainHead[u];
            hld(ch);
        }
        for(int v:g[u]){
            if(v==par[u] || v==ch)continue;
            hld(v);
        }
    }
    void dfs1(int[][] g, int[] par, int[] sub, int[] de, int u){
        sub[u] = 1;
        for(int v:g[u]){
            de[v] = de[u]+1;
            par[v] = u;
            dfs1(g, par, sub, de, v);
            sub[u]+=sub[v];
        }
    }


    class SegmentTree{
        private long initValue(){return -1;}
        private long update(long oldValue, long newValue){return newValue;}
        private long merge(long le, long ri){return Math.max(le, ri);}
        private long initQuery(){return -1;}

        int m= 1;
        long[] t;
        public SegmentTree(int n){
            while(m<n)m<<=1;
            t = new long[m<<1];
            Arrays.fill(t, initValue());
        }
        public SegmentTree(long[] a){
            while(m<a.length)m<<=1;
            t = new long[m<<1];
            Arrays.fill(t, initValue());
            for(int i = 0; i< a.length; i++)t[i+m] = a[i];
            for(int i = m-1; i>0; i--)t[i] = merge(t[i<<1], t[i<<1|1]);
        }
        public void update(int i, long val){
            t[i += m]  = update(t[i], val);
            for(i>>=1;i>0;i>>=1)t[i] = merge(t[i<<1], t[i<<1|1]);
        }
        long query(int l, int r){
            long lans = initQuery(), rans = initQuery();
            for(l+=m,r+=m+1;l<r;l>>=1,r>>=1){
                if((l&1)==1)lans = merge(lans, t[l++]);
                if((r&1)==1)rans = merge(t[--r], rans);
            }
            return merge(lans, rans);
        }
    }


    static class AhoCorasick {
        int root, sentinal, ID, A, maxSize;
        int[] next, fail, hit;
        int[] strIndex;
        public AhoCorasick(int A, int maxSize) {
            this.A = A;
            this.maxSize = maxSize + 2;
            next = new int[A * this.maxSize];
            fail = new int[this.maxSize];
//            hit = new int[this.maxSize];
            strIndex = new int[this.maxSize];
            Arrays.fill(strIndex, -1);
            Arrays.fill(fail, -1);
            Arrays.fill(next, -1);
            ID = 0;
            sentinal = ID++;
            root = ID++;
            fail[root] = sentinal;
            for (int i = 0; i < this.A; i++) next[sentinal * this.A + i] = root;
        }

        int f(char ch) {
            return ch - 'a';
        }

        int addString(int ind, char[] pat) {
            int node = root;
            for (char ch : pat) {
                int c = f(ch);
                if (next[node * A + c] == -1) next[node * A + c] = ID++;
                node = next[node * A + c];
            }
            strIndex[node] = ind;
            return node;
//            hit[node]++;
        }
        int move(int node, char ch){
            int c = ch-'a';
            while(next[node*A+c] == -1)node = fail[node];
            return next[node*A+c];
        }
        void buildSuffixLinks(){
            int[] Q = new int[ID];
            int c = 0;
            Q[c++] = root;
            for(int r = 0; r< c; r++){
                int node = Q[r];
                for(int i = 0; i< A; i++){
                    int nxt = next[node*A+i];
                    if(nxt == -1)continue;
                    Q[c++] = nxt;
                    for(int to = fail[node]; true; to = fail[to]){
                        int fch = next[to*A+i];
                        if(fch != -1){
                            fail[nxt] = fch;
//                            hit[nxt] += hit[fch];
                            break;
                        }
                    }
                }
            }
        }
        int[][] slt(){
            int cnt = 0;
            int[][] e = new int[ID][];
            for(int i = 0; i< ID; i++)if(fail[i] != -1)e[cnt++] = new int[]{fail[i], i};
            return Arrays.copyOf(e, cnt);
        }
        static char[] rev_(char[] a) {
            for (int i = 0, j = a.length - 1; i < j; i++, j--) {
                char c = a[i];
                a[i] = a[j];
                a[j] = c;
            }
            return a;
        }
    }
        //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    void exit(boolean b){if(!b)System.exit(0);}
    static void dbg(Object... o){System.err.println(Arrays.deepToString(o));}
    final long IINF = (long)1e17;
    final int INF = (int)1e9+2;
    DecimalFormat df = new DecimalFormat("0.00000000000");
    double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-8;
    static boolean multipleTC = false, memory = false, fileIO = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        long ct = System.currentTimeMillis();
        if (fileIO) {
            in = new FastReader("");
            out = new PrintWriter("");
        } else {
            in = new FastReader();
            out = new PrintWriter(System.out);
        }
        //Solution Credits: Taranpreet Singh
        int T = multipleTC? ni():1;
        pre();
        for (int t = 1; t <= T; t++) solve(t);
        out.flush();
        out.close();
        System.err.println(System.currentTimeMillis() - ct);
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();System.exit(1);}}}, "1", 1 << 28).start();
        else new Main().run();
    }
    int[][] make(int n, int e, int[] from, int[] to, boolean f){
        int[][] g = new int[n][];int[]cnt = new int[n];
        for(int i = 0; i< e; i++){
            cnt[from[i]]++;
            if(f)cnt[to[i]]++;
        }
        for(int i = 0; i< n; i++)g[i] = new int[cnt[i]];
        for(int i = 0; i< e; i++){
            g[from[i]][--cnt[from[i]]] = to[i];
            if(f)g[to[i]][--cnt[to[i]]] = from[i];
        }
        return g;
    }
    int[][][] makeS(int n, int e, int[] from, int[] to, boolean f){
        int[][][] g = new int[n][][];int[]cnt = new int[n];
        for(int i = 0; i< e; i++){
            cnt[from[i]]++;
            if(f)cnt[to[i]]++;
        }
        for(int i = 0; i< n; i++)g[i] = new int[cnt[i]][];
        for(int i = 0; i< e; i++){
            g[from[i]][--cnt[from[i]]] = new int[]{to[i], i, 0};
            if(f)g[to[i]][--cnt[to[i]]] = new int[]{from[i], i, 1};
        }
        return g;
    }
    int find(int[] set, int u){return set[u] = (set[u] == u?u:find(set, set[u]));}
    int digit(long s){int ans = 0;while(s>0){s/=10;ans++;}return ans;}
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object... o){for(Object oo:o)out.print(oo+" ");}
    void pn(Object... o){for(Object oo:o)out.print(oo+" ");out.println();}
    void pni(Object... o){for(Object oo:o)out.print(oo+" ");out.println();out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str;
            try{
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }
            return str;
        }
    }
}