#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e9;
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
int n, q, A[N], T[N], L[N], R[N], SEGMX[N << 2];
long long ANS[N];
string TMP[N], S[N], Q[N];
struct Node {
  int pre, suf, mx;
  bool flag;
  Node() {}
  Node(int _pre, int _suf, int _mx, bool _flag)
      : pre(_pre), suf(_suf), mx(_mx), flag(_flag) {}
} SEG[N << 2];
Node Merge(const Node &x, const Node &y) {
  return Node(x.pre + x.flag * y.pre, y.suf + y.flag * x.suf,
              max(x.suf + y.pre, max(x.mx, y.mx)), x.flag & y.flag);
}
void UpdateMX(int p, int x, int id = 1, int s = 0, int e = n) {
  if (e - s < 2) {
    SEGMX[id] = x;
    return;
  }
  int md = (s + e) >> 1;
  if (p < md)
    UpdateMX(p, x, id << 1, s, md);
  else
    UpdateMX(p, x, id << 1 | 1, md, e);
  SEGMX[id] = max(SEGMX[id << 1], SEGMX[id << 1 | 1]);
}
void Update(int p, bool x, int id = 1, int s = 0, int e = n) {
  if (e - s < 2) {
    SEG[id] = Node(x, x, x, x);
    return;
  }
  int md = (s + e) >> 1;
  if (p < md)
    Update(p, x, id << 1, s, md);
  else
    Update(p, x, id << 1 | 1, md, e);
  SEG[id] = Merge(SEG[id << 1], SEG[id << 1 | 1]);
}
int GetMX(int l, int r, int id = 1, int s = 0, int e = n) {
  if (l >= e || s >= r) return 0;
  if (l <= s && e <= r) return SEGMX[id];
  int md = (s + e) >> 1;
  return max(GetMX(l, r, id << 1, s, md), GetMX(l, r, id << 1 | 1, md, e));
}
Node Get(int l, int r, int id = 1, int s = 0, int e = n) {
  if (l >= e || s >= r) return Node(0, 0, 0, 0);
  if (l <= s && e <= r) return SEG[id];
  int md = (s + e) >> 1;
  return Merge(Get(l, r, id << 1, s, md), Get(l, r, id << 1 | 1, md, e));
}
int LCP(string &s, string &t) {
  int ans = 0;
  while (ans < (int)(s.size()) && ans < (int)(t.size()) && s[ans] == t[ans])
    ans++;
  return ans;
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> q;
  vector<int> comp;
  for (int i = 0; i < n; i++)
    cin >> S[i], TMP[i] = S[i], UpdateMX(i, (int)(S[i].size()));
  for (int i = 0; i < n - 1; i++) comp.push_back(LCP(TMP[i], TMP[i + 1]));
  for (int i = 0; i < q; i++) {
    cin >> T[i] >> L[i];
    L[i]--;
    if (T[i] == 1) {
      cin >> R[i];
      ANS[i] = GetMX(L[i], R[i]);
    } else {
      cin >> Q[i];
      TMP[L[i]] = Q[i];
      UpdateMX(L[i], (int)(Q[i].size()));
      if (L[i]) comp.push_back(LCP(TMP[L[i] - 1], TMP[L[i]]));
      if (n - 1 - L[i]) comp.push_back(LCP(TMP[L[i]], TMP[L[i] + 1]));
    }
  }
  sort(comp.begin(), comp.end());
  comp.resize(unique(comp.begin(), comp.end()) - comp.begin());
  for (int x : comp) {
    for (int i = 0; i < n; i++) TMP[i] = S[i];
    for (int i = 0; i < n - 1; i++) Update(i, LCP(TMP[i], TMP[i + 1]) >= x);
    for (int i = 0; i < q; i++) {
      if (T[i] == 1) {
        int len = Get(L[i], R[i] - 1).mx + 1;
        if (len == 1) len = 0;
        ANS[i] = max(ANS[i], 1LL * len * x);
      } else {
        TMP[L[i]] = Q[i];
        if (L[i]) Update(L[i] - 1, LCP(TMP[L[i] - 1], TMP[L[i]]) >= x);
        if (n - 1 - L[i]) Update(L[i], LCP(TMP[L[i]], TMP[L[i] + 1]) >= x);
      }
    }
  }
  for (int i = 0; i < q; i++)
    if (T[i] == 1) cout << ANS[i] << "\n";
  return 0;
}
