#include <bits/stdc++.h>
using namespace std;
int n, Q, a[100005];
string s[100005];
int LCP(const string &a, const string &b) {
  int r = 0;
  for (; r < a.size() && r < b.size() && a[r] == b[r]; r++)
    ;
  return r;
}
int lc[100005 * 100], rc[100005 * 100], lx[100005 * 100], rx[100005 * 100],
    mx[100005 * 100], sz[100005 * 100], bin[100005 * 100], tot, rt[100005];
int newnode() {
  int r = 0;
  if (bin[0]) {
    r = bin[bin[0]--];
    lc[r] = rc[r] = lx[r] = rx[r] = mx[r] = sz[r] = 0;
  } else
    r = ++tot;
  return r;
}
void upd(int u, int l, int m, int r) {
  sz[u] = sz[lc[u]] + sz[rc[u]];
  lx[u] = (lx[lc[u]] == m - l + 1 ? lx[rc[u]] : 0) + lx[lc[u]];
  rx[u] = (rx[rc[u]] == r - m ? rx[lc[u]] : 0) + rx[rc[u]];
  mx[u] = max(mx[lc[u]], max(mx[rc[u]], lx[rc[u]] + rx[lc[u]]));
}
void ins(int &u, int l, int r, int p, int v) {
  if (!u) u = newnode();
  sz[u] += v;
  if (l == r) {
    lx[u] = rx[u] = mx[u] = sz[u];
    if (!sz[u]) bin[++bin[0]] = u, u = 0;
    return;
  }
  int m = l + r >> 1;
  p <= m ? ins(lc[u], l, m, p, v) : ins(rc[u], m + 1, r, p, v);
  upd(u, l, m, r);
  if (!sz[u]) bin[++bin[0]] = u, u = 0;
}
void qry(int u, int l, int r, int ql, int qr, int &MX, int &RX) {
  if (ql > r || l > qr || !u) return (void)(RX = 0);
  if (ql <= l && r <= qr)
    return (void)(MX = max(MX, max(mx[u], RX + lx[u])),
                  RX = (rx[u] == r - l + 1 ? RX : 0) + rx[u]);
  int m = l + r >> 1;
  qry(lc[u], l, m, ql, qr, MX, RX), qry(rc[u], m + 1, r, ql, qr, MX, RX);
}
int c[100005];
bool cmp(const int &u, const int &v) { return a[u] > a[v]; }
int F[100005], SZ[100005];
int Find(int u) { return !F[u] ? u : F[u] = Find(F[u]); }
set<int> mS, mA;
namespace SGT {
int mx[100005 << 2];
void ins(int u, int l, int r, int p, int v) {
  if (l == r) return (void)(mx[u] = v);
  int m = l + r >> 1;
  p <= m ? ins(u << 1, l, m, p, v) : ins(u << 1 | 1, m + 1, r, p, v);
  mx[u] = max(mx[u << 1], mx[u << 1 | 1]);
}
int qry(int u, int l, int r, int ql, int qr) {
  if (l > qr || ql > r) return 0;
  if (ql <= l && r <= qr) return mx[u];
  int m = l + r >> 1;
  return max(qry(u << 1, l, m, ql, qr), qry(u << 1 | 1, m + 1, r, ql, qr));
}
}  // namespace SGT
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> Q;
  for (int i = (1), LIM = (n); i <= LIM; i++) {
    cin >> s[i];
    SGT::ins(1, 1, n, i, s[i].length());
    if (i > 1) {
      a[i - 1] = LCP(s[i - 1], s[i]);
      if (a[i - 1] >= 350) mA.insert(i - 1);
      for (int j = (1), LIM = (min(a[i - 1], 350)); j <= LIM; j++)
        ins(rt[j], 1, n - 1, i - 1, 1);
    }
  }
  for (int op, l, r; Q--;) {
    cin >> op >> l;
    if (op == 1) {
      cin >> r;
      long long ans = SGT::qry(1, 1, n, l, r);
      c[0] = 0;
      for (int v : mA)
        if (l <= v && v < r)
          c[++c[0]] = v, F[v] = F[v + 1] = 0, SZ[v] = SZ[v + 1] = 1;
      sort(c + 1, c + c[0] + 1, cmp);
      for (int i = (1), LIM = (c[0]); i <= LIM; i++) {
        int u = c[i], v = u + 1;
        F[v] = Find(u);
        SZ[Find(u)] += SZ[v];
        ans = max(ans, 1ll * SZ[Find(u)] * a[u]);
      }
      for (int i = (1), LIM = (350); i <= LIM; i++) {
        int MX = 0, RX = 0;
        qry(rt[i], 1, n - 1, l, r - 1, MX, RX);
        if (MX) ans = max(ans, 1ll * (MX + 1) * i);
      }
      printf("%lld\n", ans);
    } else {
      if (l > 1) {
        if (a[l - 1] >= 350) mA.erase(l - 1);
        for (int j = (1), LIM = (min(a[l - 1], 350)); j <= LIM; j++)
          ins(rt[j], 1, n - 1, l - 1, -1);
      }
      if (l < n) {
        if (a[l] >= 350) mA.erase(l);
        for (int j = (1), LIM = (min(a[l], 350)); j <= LIM; j++)
          ins(rt[j], 1, n - 1, l, -1);
      }
      cin >> s[l];
      SGT::ins(1, 1, n, l, s[l].length());
      if (l > 1) {
        a[l - 1] = LCP(s[l - 1], s[l]);
        if (a[l - 1] >= 350) mA.insert(l - 1);
        for (int j = (1), LIM = (min(a[l - 1], 350)); j <= LIM; j++)
          ins(rt[j], 1, n - 1, l - 1, 1);
      }
      if (l < n) {
        a[l] = LCP(s[l], s[l + 1]);
        if (a[l] >= 350) mA.insert(l);
        for (int j = (1), LIM = (min(a[l], 350)); j <= LIM; j++)
          ins(rt[j], 1, n - 1, l, 1);
      }
    }
  }
}
