#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], l[N], r[N], t[N], id[N], mark[N], mx[N << 2], n, q, x;
long long ans[N];
string s[N], S[N], que[N];
vector<int> vec;
void SET(int l, int r, int val, int L = 0, int R = n, int id = 1) {
  if (r <= L || R <= l) return;
  if (l <= L && R <= r) {
    mx[id] = val;
    return;
  }
  SET(l, r, val, L, (L + R) >> 1, id << 1);
  SET(l, r, val, (L + R) >> 1, R, id << 1 | 1);
  mx[id] = max(mx[id << 1], mx[id << 1 | 1]);
  return;
}
int GET(int l, int r, int L = 0, int R = n, int id = 1) {
  if (r <= L || R <= l) return 0;
  if (l <= L && R <= r) return mx[id];
  int x1 = GET(l, r, L, (L + R) >> 1, id << 1);
  int x2 = GET(l, r, (L + R) >> 1, R, id << 1 | 1);
  return max(x1, x2);
}
struct Node {
  int Max = 0, pref = 0, suff = 0, full = 0;
} seg[N << 2], Null;
Node Merge(Node &x, Node &y) {
  Node res;
  res.pref = x.pref + (x.full ? y.pref : 0);
  res.suff = y.suff + (y.full ? x.suff : 0);
  res.full = x.full && y.full;
  res.Max = max(x.suff + y.pref, max(x.Max, y.Max));
  return res;
}
void Set(int l, int r, int val, int L = 0, int R = n - 1, int id = 1) {
  if (r <= L || R <= l) return;
  if (l <= L && R <= r) {
    seg[id].Max = seg[id].pref = seg[id].suff = seg[id].full = val;
    return;
  }
  Set(l, r, val, L, (L + R) >> 1, id << 1);
  Set(l, r, val, (L + R) >> 1, R, id << 1 | 1);
  seg[id] = Merge(seg[id << 1], seg[id << 1 | 1]);
  return;
}
Node Get(int l, int r, int L = 0, int R = n - 1, int id = 1) {
  if (r <= L || R <= l) return Null;
  if (l <= L && R <= r) return seg[id];
  Node x1 = Get(l, r, L, (L + R) >> 1, id << 1);
  Node x2 = Get(l, r, (L + R) >> 1, R, id << 1 | 1);
  return Merge(x1, x2);
}
int LCP(string &s, string &t) {
  int res = 0;
  while (res < s.size() && res < t.size() && s[res] == t[res]) res++;
  return res;
}
void Init() {
  for (int i = 0; i < n; i++) s[i] = S[i];
  for (int i = 0; i < n - 1; i++) {
    a[i] = LCP(s[i], s[i + 1]);
    if (a[i] >= x)
      Set(i, i + 1, 1);
    else
      Set(i, i + 1, 0);
  }
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> q;
  for (int i = 0; i < n; i++)
    cin >> S[i], s[i] = S[i], SET(i, i + 1, S[i].size());
  for (int i = 0; i < n - 1; i++) {
    a[i] = LCP(s[i], s[i + 1]);
    if (!mark[a[i]]) {
      vec.push_back(a[i]);
      mark[a[i]] = 1;
    }
  }
  for (int i = 0; i < q; i++) {
    cin >> t[i];
    if (t[i] == 1) {
      cin >> l[i] >> r[i];
      l[i]--;
      ans[i] = GET(l[i], r[i]);
      r[i]--;
    }
    if (t[i] == 2) {
      cin >> id[i] >> que[i], id[i]--;
      s[id[i]] = que[i];
      SET(id[i], id[i] + 1, que[i].size());
      if (id[i] - 1 >= 0) {
        a[id[i] - 1] = LCP(s[id[i] - 1], s[id[i]]);
        if (!mark[a[id[i] - 1]]) {
          mark[a[id[i] - 1]] = 1;
          vec.push_back(a[id[i] - 1]);
        }
      }
      if (id[i] + 1 < n) {
        a[id[i]] = LCP(s[id[i]], s[id[i] + 1]);
        if (!mark[a[id[i]]]) {
          mark[a[id[i]]] = 1;
          vec.push_back(a[id[i]]);
        }
      }
    }
  }
  for (int _ = 0; _ < vec.size(); _++) {
    x = vec[_];
    Init();
    for (int i = 0; i < q; i++) {
      if (t[i] == 1) {
        int A = Get(l[i], r[i]).Max;
        if (A != 0) ans[i] = max(ans[i], (A + 1ll) * (x + 0ll));
      }
      if (t[i] == 2) {
        s[id[i]] = que[i];
        if (id[i] - 1 >= 0) {
          a[id[i] - 1] = LCP(s[id[i] - 1], s[id[i]]);
          if (a[id[i] - 1] >= x)
            Set(id[i] - 1, id[i], 1);
          else
            Set(id[i] - 1, id[i], 0);
        }
        if (id[i] + 1 < n) {
          a[id[i]] = LCP(s[id[i]], s[id[i] + 1]);
          if (a[id[i]] >= x)
            Set(id[i], id[i] + 1, 1);
          else
            Set(id[i], id[i] + 1, 0);
        }
      }
    }
  }
  for (int i = 0; i < q; i++)
    if (t[i] == 1) cout << ans[i] << " ";
  return 0;
}
