#include <bits/stdc++.h>
using namespace std;
class segtree {
 private:
  using T = array<int, 4>;
  int b;
  vector<T> tr;
  T merge(const T& x, const T& y) {
    T ret = {};
    ret[0] = max({x[0], y[0], x[2] + y[1]});
    ret[1] = (x[1] == x[3] ? x[3] + y[1] : x[1]);
    ret[2] = (y[2] == y[3] ? x[2] + y[3] : y[2]);
    ret[3] = x[3] + y[3];
    return ret;
  }
  T single(int x = -1) {
    T ret = {};
    for (int j = 0; j < 3; j++) {
      ret[j] = (x >= LB);
    }
    ret[3] = 1;
    return ret;
  }

 public:
  int LB;
  segtree() {}
  segtree(int lowerBound, const vector<int>& a) {
    LB = lowerBound;
    b = 1;
    while (b < (int)a.size()) {
      b <<= 1;
    }
    tr.assign(2 * b, single());
    for (int i = 0; i < (int)a.size(); i++) {
      tr[i + b] = single(a[i]);
    }
    for (int i = b - 1; i > 0; i--) {
      tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }
  }
  void asign(int lowerBound, const vector<int>& a) {
    LB = lowerBound;
    for (int i = 0; i < b; i++) {
      tr[i + b] = single(i < (int)a.size() ? a[i] : -1);
    }
    for (int i = b - 1; i > 0; i--) {
      tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }
  }
  void upd(int i, int v) {
    tr[i += b] = single(v);
    for (i >>= 1; i > 0; i >>= 1) {
      tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }
  }
  int qry(int l, int r) {
    T ansr = {}, ansl = {};
    for (l += b, r += b; l <= r; l >>= 1, r >>= 1) {
      if (l & 1) ansl = merge(ansl, tr[l++]);
      if (!(r & 1)) ansr = merge(tr[r--], ansr);
    }
    return merge(ansl, ansr)[0];
  }
};
class M_segtree {
 private:
  using T = int;
  int b;
  vector<T> tr;
  T merge(const T& x, const T& y) { return max(x, y); }
  T single(int x = 0) { return x; }

 public:
  M_segtree() {}
  M_segtree(const vector<int>& a) {
    b = 1;
    while (b < (int)a.size()) {
      b <<= 1;
    }
    tr.assign(2 * b, single());
    for (int i = 0; i < (int)a.size(); i++) {
      tr[i + b] = single(a[i]);
    }
    for (int i = b - 1; i > 0; i--) {
      tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }
  }
  void upd(int i, int v) {
    tr[i += b] = single(v);
    for (i >>= 1; i > 0; i >>= 1) {
      tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }
  }
  int qry(int l, int r) {
    int ans = 0;
    for (l += b, r += b; l <= r; l >>= 1, r >>= 1) {
      if (l & 1) ans = max(ans, tr[l++]);
      if (!(r & 1)) ans = max(ans, tr[r--]);
    }
    return ans;
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, q;
  cin >> n >> q;
  vector<string> s(n);
  vector<int> LN(n, 0);
  set<int> Vals;
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    LN[i] = s[i].length();
    Vals.insert(LN[i]);
  }
  auto LCP = [](const string& ss, const string& t) {
    for (int i = 0; i < (int)min(ss.length(), t.length()); i++) {
      if (ss[i] != t[i]) {
        return i;
      }
    }
    return (int)min(ss.length(), t.length());
  };
  vector<int> OP(q), L(q), R(q), res(q, 0), Lcp(n - 1, 0);
  vector<vector<pair<int, int>>> qc(q);
  for (int i = 1; i < n; i++) {
    Lcp[i - 1] = LCP(s[i - 1], s[i]);
    Vals.insert(Lcp[i - 1]);
  }
  vector<int> lcp = Lcp;
  for (int tt = 0; tt < q; tt++) {
    cin >> OP[tt];
    if (OP[tt] == 1) {
      cin >> L[tt] >> R[tt];
      --L[tt];
      --R[tt];
    } else {
      string t;
      cin >> L[tt] >> t;
      --L[tt];
      R[tt] = t.length();
      Vals.insert(R[tt]);
      s[L[tt]] = t;
      if (L[tt] > 0) {
        lcp[L[tt] - 1] = LCP(s[L[tt] - 1], s[L[tt]]);
        qc[tt].emplace_back(L[tt] - 1, lcp[L[tt] - 1]);
        Vals.insert(lcp[L[tt] - 1]);
      }
      if (L[tt] + 1 < n) {
        lcp[L[tt]] = LCP(s[L[tt]], s[L[tt] + 1]);
        qc[tt].emplace_back(L[tt], lcp[L[tt]]);
        Vals.insert(lcp[L[tt]]);
      }
    }
  }
  segtree st(INT_MAX, Lcp);
  for (int mn : Vals) {
    st.asign(mn, Lcp);
    for (int tt = 0; tt < q; tt++) {
      if (OP[tt] == 1) {
        int a = L[tt], b = R[tt];
        int& ans = res[tt];
        if (a < b) {
          int z = st.qry(a, b - 1);
          ans = max(ans, mn * (z + (z > 0)));
        }
      } else {
        for (const auto& p : qc[tt]) {
          st.upd(p.first, p.second);
        }
      }
    }
  }
  M_segtree lns(LN);
  for (int tt = 0; tt < q; tt++) {
    if (OP[tt] == 1) {
      cout << max(res[tt], lns.qry(L[tt], R[tt])) << '\n';
    } else {
      lns.upd(L[tt], R[tt]);
    }
  }
  return 0;
}
