Problem: Mahmoud and Ehab solved Dr. Evil's questions so he gave them the password of the door of the evil land. When they tried to open the door using it, the door gave them a final question to solve before they leave (yes, the door is digital, Dr. Evil is modern). If they don't solve it, all the work will be useless and they won't leave the evil land forever. Will you help them?

Mahmoud and Ehab are given n strings s1, s2, ... , sn numbered from 1 to n and q queries, Each query has one of the following forms:

  * 1 a b (1 ≤ a ≤ b ≤ n), For all the intervals [l;r] where (a ≤ l ≤ r ≤ b) find the maximum value of this expression:

(r - l + 1) * LCP(sl, sl + 1, ... , sr - 1, sr) where LCP(str1, str2, str3, ... ) is the length of the longest common prefix of the strings str1, str2, str3, ... .

  * 2 x y (1 ≤ x ≤ n) where y is a string, consisting of lowercase English letters. Change the string at position x to y.

Input

The first line of input contains 2 integers n and q (1 ≤ n ≤ 105, 1 ≤ q ≤ 105) – The number of strings and the number of queries, respectively.

The second line contains n strings stri consisting of lowercase English letters.

The next q lines describe the queries and may have one of the 2 forms:

  * 1 a b (1 ≤ a ≤ b ≤ n).
  * 2 x y (1 ≤ x ≤ n), where y is a string consisting of lowercase English letters.



the total length of all strings in input won't exceed 105

Output

For each query of first type output its answer in a new line.

Example

Input

5 9
mahmoud mahmoudbadawy drmahmoud drevil mahmoud
1 1 5
1 1 2
1 2 3
2 3 mahmoud
2 4 mahmoud
2 2 mahmouu
1 1 5
1 2 3
1 1 1


Output

14
14
13
30
12
7

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Solution {


    static MyScanner sc;
    private static PrintWriter out;
    static long M = 1000000007;


    public static void main(String[] s) throws Exception {
        StringBuilder stringBuilder = new StringBuilder();


//        stringBuilder.append("100000 100000 ");
//        Random r = new Random(5);
//        for (int i = 0; i < 100000; i++) {
//            for (int j = 0; j < 4; j++) {
//                stringBuilder.append((char) (r.nextInt(2) + 'a'));
//            }
//            stringBuilder.append(' ');
//        }
//        for (int i = 0; i < 100000; i++) {
//            stringBuilder.append("1 ");
//            stringBuilder.append(r.nextInt(10) + 2);
//            stringBuilder.append(' ');
//            stringBuilder.append(r.nextInt(10) + 12);
//            stringBuilder.append(' ');
//        }

//
//        stringBuilder.append("10 20\n" +
//                "qn jq wkcexecmdkm bak xrkjwqdyu ossvo oat mbyx xnagxbwe gzay\n" +
//                "2 7 onzpq\n" +
//                "1 4 10\n" +
//                "2 9 xnagta\n" +
//                "2 7 o\n" +
//                "2 7 y\n" +
//                "1 5 6\n" +
//                "1 1 2\n" +
//                "2 2 jhulkujid\n" +
//                "1 3 10\n" +
//                "2 7 cl\n" +
//                "1 3 6\n" +
//                "1 5 10\n" +
//                "1 1 5\n" +
//                "2 3 wkc\n" +
//                "1 3 6\n" +
//                "2 1 qnwvjal\n" +
//                "2 1 qnwvncksizgza\n" +
//                "2 4 bh\n" +
//                "1 3 6\n" +
//                "1 7 10");
//

        if (stringBuilder.length() == 0) {
            sc = new MyScanner(System.in);
        } else {
            sc = new MyScanner(new BufferedReader(new StringReader(stringBuilder.toString())));
        }

        out = new PrintWriter(new OutputStreamWriter(System.out));

        initData();
        solve();
        out.flush();
    }


    private static void initData() {
    }

    private static int n;


    private static void solve() throws IOException {
        n = sc.nextInt();
        int m = sc.nextInt();


        STree s1 = new STree(n, true);

        int[] mmm = new int[n - 1];


        String[] k = new String[n];
        for (int i = 0; i < n; i++) {
            k[i] = sc.next();
            s1.put(i, k[i].length());
            if (i > 0) {
                mmm[i - 1] = lcp(k[i], k[i - 1]);
            }
        }
        SegmentTreeSegPos segmentTreeSegPos = new SegmentTreeSegPos(mmm);

        for (int r = 0; r < m; r++) {
            int t = sc.nextInt();
            if (t == 1) {
                int ll = sc.nextInt() - 1;
                int rr = sc.nextInt() - 1;
                long v1 = s1.max(ll, rr);
                if (rr > ll) {
                    v1 = Math.max(segmentTreeSegPos.max(ll, rr), v1);
                }
                out.println(v1);
            } else {
                int p = sc.nextInt() - 1;
                String ttt = sc.next();
                k[p] = ttt;
                s1.put(p, ttt.length());
                if (p > 0) {
                    mmm[p - 1] = lcp(k[p], k[p - 1]);
                    segmentTreeSegPos.update(p - 1, mmm[p - 1]);
                }
                if (p < n - 1) {
                    mmm[p] = lcp(k[p], k[p + 1]);
                    segmentTreeSegPos.update(p, mmm[p]);
                }
            }
        }

    }


    public static class SegmentTreeSegPos {
        public int M, H, N;
        public int[][] vasc;
        public int[][] pasc;
        public int[][] vdesc;
        public int[][] pdesc;
        public long[] maxs;
        public int[] lens;

        // one word
        public SegmentTreeSegPos(int[] a) {
            N = a.length;
            M = Integer.highestOneBit(Math.max(N - 1, 1)) << 2;
            H = M >>> 1;
            vasc = new int[M][];
            pasc = new int[M][];
            vdesc = new int[M][];
            pdesc = new int[M][];
            maxs = new long[M];
            lens = new int[M];
            for (int i = 0; i < N; i++) {
                vasc[H + i] = new int[]{a[i]};
                pasc[H + i] = new int[]{0}; // first appeared
                vdesc[H + i] = new int[]{a[i]};
                pdesc[H + i] = new int[]{0}; // last appeared
                maxs[H + i] = a[i] * 2;
                lens[H + i] = 1;
            }
            for (int i = N; i < H; i++) {
                vasc[H + i] = new int[0];
                pasc[H + i] = new int[0];
                vdesc[H + i] = new int[0];
                pdesc[H + i] = new int[0];
                lens[H + i] = 0;
            }
            for (int i = H - 1; i >= 1; i--) {
                propagate(i);
            }
        }
        // v:desc
        // p:asc

        int[][] merge(int[] v1, int[] p1, int[] v2, int[] p2) {
            int[] rv = Arrays.copyOf(v2, v2.length + v1.length);
            int[] rp = Arrays.copyOf(p2, v2.length + v1.length);
            int p = v2.length;
            int last = p > 0 ? p2[p - 1] : -1;
            for (int i = 0; i < v1.length; i++) {
                if (p > 0 && rv[p - 1] <= v1[i]) {
                    rp[p - 1] = p2[p - 1] + p1[i] + 1;
                } else if (p == 0 || rv[p - 1] > v1[i]) {
                    rv[p] = v1[i];
                    rp[p++] = last + p1[i] + 1;
                }
            }
//			tr(v1, p1, v2, p2, rv, rp);
            return new int[][]{
                    Arrays.copyOf(rv, p),
                    Arrays.copyOf(rp, p)
            };
        }

        private void tr(Object... o) {
            System.out.println(Arrays.deepToString(o));
        }

        private void propagate(int i) {
            int[][] res = merge(vasc[2 * i], pasc[2 * i], vasc[2 * i + 1], pasc[2 * i + 1]);
            vasc[i] = res[0];
            pasc[i] = res[1];

            res = merge(vdesc[2 * i + 1], pdesc[2 * i + 1], vdesc[2 * i], pdesc[2 * i]);
            vdesc[i] = res[0];
            pdesc[i] = res[1];

            lens[i] = lens[2 * i] + lens[2 * i + 1];
            maxs[i] = Math.max(maxs[2 * i], maxs[2 * i + 1]);

            {
                int[] L = vasc[2 * i], R = vdesc[2 * i + 1];
                int[] LP = pasc[2 * i], RP = pdesc[2 * i + 1];
                int k = 0;
                for (int j = 0; j < L.length; j++) {
                    while (k < R.length && R[k] >= L[j]) {
                        k++;
                    }
                    if (k == 0) continue;
                    int right = RP[k - 1];
                    int left = LP[j];
                    long val = (long) (left + right + 3) * L[j];
//					tr(L, R, LP, RP, left, right, val);
                    maxs[i] = Math.max(maxs[i], val);
                }
            }
            {
                int[] R = vasc[2 * i], L = vdesc[2 * i + 1];
                int[] RP = pasc[2 * i], LP = pdesc[2 * i + 1];
                int k = 0;
                for (int j = 0; j < L.length; j++) {
                    while (k < R.length && R[k] >= L[j]) {
                        k++;
                    }
                    if (k == 0) continue;
                    int right = RP[k - 1];
                    int left = LP[j];
                    long val = (long) (left + right + 3) * L[j];
                    maxs[i] = Math.max(maxs[i], val);
                }
            }
        }

        public static int[] rev(int[] a) {
            int[] b = new int[a.length];
            for (int i = 0; i < a.length; i++) b[a.length - 1 - i] = a[i];
            return b;
        }


        public void update(int pos, int v) {
            vasc[H + pos][0] = v;
            vdesc[H + pos][0] = v;
            maxs[H + pos] = vasc[H + pos][0] * 2;
            for (int i = H + pos >>> 1; i >= 1; i >>>= 1) {
                propagate(i);
            }
        }

        public long max(int l, int r) {
            gmax = Long.MIN_VALUE;
            max(l, r, 0, H, 1);
            return gmax;
        }

        long gmax;

        private int[][] max(int l, int r, int cl, int cr, int cur) {
            if (l <= cl && cr <= r) {
                gmax = Math.max(gmax, maxs[cur]);
                return new int[][]{vasc[cur], pasc[cur], vdesc[cur], pdesc[cur]};
            } else {
                int mid = cl + cr >>> 1;
                int[][] LX = null, RX = null;
                if (cl < r && l < mid) {
                    LX = max(l, r, cl, mid, 2 * cur);
                }
                if (mid < r && l < cr) {
                    RX = max(l, r, mid, cr, 2 * cur + 1);
                }

                if (LX == null) return RX;
                if (RX == null) return LX;

                int[][] ret = new int[4][];
                int[][] res = merge(LX[0], LX[1], RX[0], RX[1]);
                ret[0] = res[0];
                ret[1] = res[1];

                res = merge(RX[2], RX[3], LX[2], LX[3]);
                ret[2] = res[0];
                ret[3] = res[1];

                {
                    int[] L = LX[0], R = RX[2];
                    int[] LP = LX[1], RP = RX[3];
                    int k = 0;
                    for (int j = 0; j < L.length; j++) {
                        while (k < R.length && R[k] >= L[j]) {
                            k++;
                        }
                        if (k == 0) continue;
                        int right = RP[k - 1];
                        int left = LP[j];
                        long val = (long) (left + right + 3) * L[j];
//						tr(L, R, LP, RP, left, right, L, val);
                        gmax = Math.max(gmax, val);
                    }
                }
                {
                    int[] R = LX[0], L = RX[2];
                    int[] RP = LX[1], LP = RX[3];
                    int k = 0;
                    for (int j = 0; j < L.length; j++) {
                        while (k < R.length && R[k] >= L[j]) {
                            k++;
                        }
                        if (k == 0) continue;
                        int right = RP[k - 1];
                        int left = LP[j];
                        long val = (long) (left + right + 3) * L[j];
                        gmax = Math.max(gmax, val);
                    }
                }
                return ret;
            }
        }
    }


    private static int lcp(String s, String s1) {
        int m = 0;
        for (int i = 0; i < Math.min(s.length(), s1.length()); i++) {
            if (s.charAt(i) != s1.charAt(i)) break;
            m++;
        }
        return m;
    }

    private static void solveT() throws IOException {
        int t = sc.nextInt();
        while (t-- > 0) {
            solve();
        }
    }


    private static long gcd(long l, long l1) {
        if (l > l1) return gcd(l1, l);
        if (l == 0) return l1;
        return gcd(l1 % l, l);
    }

    private static long pow(long a, long b, long m) {
        if (b == 0) return 1;
        if (b == 1) return a;
        long pp = pow(a, b / 2, m);
        pp *= pp;
        pp %= m;
        return (pp * (b % 2 == 0 ? 1 : a)) % m;
    }


    static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        MyScanner(BufferedReader br) {
            this.br = br;
        }

        public MyScanner(InputStream in) {
            this(new BufferedReader(new InputStreamReader(in)));
        }

        void findToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
        }

        String next() {
            findToken();
            return st.nextToken();
        }

        Integer[] nab(int n) {
            Integer[] k = new Integer[n];
            for (int i = 0; i < n; i++) {
                k[i] = sc.fi();
            }
            return k;
        }

        int[] na(int n) {
            int[] k = new int[n];
            for (int i = 0; i < n; i++) {
                k[i] = sc.fi();
            }
            return k;
        }

        long[] nl(int n) {
            long[] k = new long[n];
            for (int i = 0; i < n; i++) {
                k[i] = sc.nextLong();
            }
            return k;
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        int fi() {
            String t = next();
            int cur = 0;
            boolean n = t.charAt(0) == '-';
            for (int a = n ? 1 : 0; a < t.length(); a++) {
                cur = cur * 10 + t.charAt(a) - '0';
            }
            return n ? -cur : cur;
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }

    private static final class STree {
        private final boolean maxt;
        int rs;
        int[] val1;
        int[] from1;
        int[] to1;
        int[] metric;

        public STree(int c, boolean maxt) {
            rs = c;
            this.maxt = maxt;
            int size = Integer.highestOneBit(c);
            if (size != c) {
                size <<= 1;
            }
            int rs = size << 1;
            val1 = new int[rs];
            from1 = new int[rs];
            metric = new int[rs];
            to1 = new int[rs];

            Arrays.fill(from1, Integer.MAX_VALUE);
            if (!maxt)
                Arrays.fill(metric, Integer.MAX_VALUE);
            for (int r = rs - 1; r > 1; r--) {
                if (r >= size) {
                    from1[r] = r - size;
                    to1[r] = r - size;
                }
                from1[r / 2] = Math.min(from1[r / 2], from1[r]);
                to1[r / 2] = Math.max(to1[r / 2], to1[r]);
            }
        }

        public STree(int c) {
            this(c, true);
        }

        public int max(int from, int to) {
            return max(1, from, to);
        }

        private int max(int cur, int from, int to) {
            if (cur >= val1.length) return 0;
            if (from <= from1[cur] && to1[cur] <= to) {
                return metric[cur];
            }
            if (from1[cur] > to || from > to1[cur]) {
                return 0;
            }
            cur <<= 1;
            return Math.max(max(cur, from, to), max(cur + 1, from, to));
        }


        public void put(int x, int val) {
            x += val1.length >> 1;
            val1[x] = val;
            metric[x] = val;
            addToParent(x);
        }


        private void addToParent(int cur) {
            while (cur > 1) {
                cur >>= 1;
                if (maxt) {
                    metric[cur] = Math.max(metric[cur << 1], metric[1 + (cur << 1)]);
                } else {
                    metric[cur] = Math.min(metric[cur << 1], metric[1 + (cur << 1)]);
                }

            }
        }

        public long x(int i) {
            return val1[i + val1.length >> 1];
        }
    }
}