#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops,fast-math")
using namespace std;
long long poww(long long a, long long b, long long md) {
  return (!b ? 1
             : (b & 1 ? a * poww(a * a % md, b / 2, md) % md
                      : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 131072;
const long long inf = 9223372036854775807;
const long long mod = 1e8 + 7;
const int sq = 250;
int type[maxn], ql[maxn], qr[maxn], n, q, lcp[maxn], seg[maxn * 4],
    pr[maxn * 4], sf[maxn * 4], ans[maxn], sz = 1, lc, rc, seg2[4 * maxn];
string s[maxn], qs[maxn], ts[maxn];
vector<int> comp;
pair<pair<int, int>, pair<int, int> > res;
void build2(const int &x = 1, const int &lx = 0, const int &rx = n) {
  if (rx - lx == 1) {
    seg2[x] = ts[lx].size();
    return;
  }
  int mid = lx + rx >> 1;
  build2(x << 1, lx, mid);
  build2(x << 1 | 1, mid, rx);
  seg2[x] = max(seg2[x << 1], seg2[x << 1 | 1]);
}
void upd2(const int &p, const int &x = 1, const int &lx = 0,
          const int &rx = n) {
  if (rx - lx == 1) {
    seg2[x] = ts[lx].size();
    return;
  }
  int mid = lx + rx >> 1;
  if (p < mid)
    upd2(p, x << 1, lx, mid);
  else
    upd2(p, x << 1 | 1, mid, rx);
  seg2[x] = max(seg2[x << 1], seg2[x << 1 | 1]);
}
int get2(const int &l, const int &r, const int &x = 1, const int &lx = 0,
         const int &rx = n) {
  if (lx >= r || rx <= l) return 0;
  if (lx >= l && rx <= r) {
    return seg2[x];
  }
  int mid = lx + rx >> 1;
  return max(get2(l, r, x << 1, lx, mid), get2(l, r, x << 1 | 1, mid, rx));
}
void merge(const int &x, const int &lx, const int &rx, const int &mid) {
  lc = x << 1;
  rc = x << 1 | 1;
  seg[x] = max(seg[lc], seg[rc]);
  seg[x] = max(seg[x], sf[lc] + pr[rc]);
  if (seg[lc] == mid - lx) {
    pr[x] = mid - lx + pr[rc];
  } else
    pr[x] = pr[lc];
  if (seg[rc] == rx - mid) {
    sf[x] = rx - mid + sf[lc];
  } else
    sf[x] = sf[rc];
}
pair<pair<int, int>, pair<int, int> > merge(
    const pair<pair<int, int>, pair<int, int> > &p1,
    const pair<pair<int, int>, pair<int, int> > &p2) {
  res = {{0, 0}, {0, 0}};
  res.first.second = p1.first.second + p2.first.second;
  res.first.first = max(p1.first.first, p2.first.first);
  res.first.first = max(res.first.first, p1.second.second + p2.second.first);
  if (p1.first.first == p1.first.second)
    res.second.first = p1.first.first + p2.second.first;
  else
    res.second.first = p1.second.first;
  if (p2.first.first == p2.first.second)
    res.second.second = p2.first.first + p1.second.second;
  else
    res.second.second = p2.second.second;
  return res;
}
void build(const int &i, const int &x = 1, const int &lx = 1,
           const int &rx = n) {
  if (rx - lx == 1) {
    if (lcp[lx] >= i) {
      seg[x] = 1;
      sf[x] = 1;
      pr[x] = 1;
    } else {
      seg[x] = sf[x] = pr[x] = 0;
    }
    return;
  }
  int mid = lx + rx >> 1;
  build(i, x << 1, lx, mid);
  build(i, x << 1 | 1, mid, rx);
  merge(x, lx, rx, mid);
}
void upd(const int &p, const int &v, const int &x = 1, const int &lx = 1,
         const int &rx = n) {
  if (rx - lx == 1) {
    seg[x] = sf[x] = pr[x] = v;
    return;
  }
  int mid = lx + rx >> 1;
  if (p < mid)
    upd(p, v, x << 1, lx, mid);
  else
    upd(p, v, x << 1 | 1, mid, rx);
  merge(x, lx, rx, mid);
}
pair<pair<int, int>, pair<int, int> > get(const int &l, const int &r,
                                          const int &x = 1, const int &lx = 1,
                                          const int &rx = n) {
  if (r <= l) return {{-1, 0}, {0, 0}};
  if (lx >= r || rx <= l) return {{-1, 0}, {0, 0}};
  if (lx >= l && rx <= r) {
    return {{seg[x], rx - lx}, {pr[x], sf[x]}};
  }
  int mid = lx + rx >> 1;
  return merge(get(l, r, x << 1, lx, mid), get(l, r, x << 1 | 1, mid, rx));
}
inline void reset() {
  for (int i = 0; i < n; i++) {
    ts[i] = s[i];
    lcp[i] = 0;
    if (i != 0) {
      for (int j = 0; j < s[i].size() && j < s[i - 1].size(); j++) {
        if (s[i][j] != s[i - 1][j]) break;
        lcp[i]++;
      }
    }
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  ;
  cin >> n >> q;
  for (int i = 0; i < n; i++) {
    cin >> s[i];
    ts[i] = s[i];
    if (i != 0) {
      for (int j = 0; j < s[i].size() && j < s[i - 1].size(); j++) {
        if (s[i][j] != s[i - 1][j]) break;
        lcp[i]++;
      }
    }
    comp.push_back(lcp[i]);
  }
  if (n == 1) {
    for (int i = 1; i <= q; i++) {
      cin >> type[i];
      if (type[i] == 1) {
        cin >> ql[i] >> qr[i];
        cout << s[0].size() << endl;
      } else
        cin >> ql[i] >> s[0];
    }
    return 0;
  }
  build2();
  for (int i = 1; i <= q; i++) {
    cin >> type[i];
    if (type[i] == 1) {
      cin >> ql[i] >> qr[i];
      ql[i]--;
      ans[i] = max(ans[i], get2(ql[i], qr[i]));
    } else {
      cin >> ql[i] >> qs[i];
      ql[i]--;
      ts[ql[i]] = qs[i];
      upd2(ql[i]);
      if (ql[i] > 0) {
        lcp[ql[i]] = 0;
        for (int j = 0; j < ts[ql[i]].size() && j < ts[ql[i] - 1].size(); j++) {
          if (ts[ql[i]][j] != ts[ql[i] - 1][j]) break;
          lcp[ql[i]]++;
        }
      }
      if (ql[i] < n - 1) {
        lcp[ql[i] + 1] = 0;
        for (int j = 0; j < ts[ql[i]].size() && j < ts[ql[i] + 1].size(); j++) {
          if (ts[ql[i]][j] != ts[ql[i] + 1][j]) break;
          lcp[ql[i] + 1]++;
        }
      }
      comp.push_back(lcp[ql[i]]);
      comp.push_back(lcp[ql[i] + 1]);
    }
  }
  comp.push_back(0);
  comp.push_back(1);
  sort((comp).begin(), (comp).end());
  comp.resize(unique((comp).begin(), (comp).end()) - comp.begin());
  int LC, o;
  for (int h = 1; h < comp.size(); h++) {
    LC = comp[h];
    reset();
    build(LC);
    for (int i = 1; i <= q; i++) {
      if (type[i] == 1) {
        o = get(ql[i] + 1, qr[i]).first.first;
        if (o > 0) ans[i] = max(ans[i], (o + 1) * LC);
        continue;
      }
      ts[ql[i]] = qs[i];
      if (ql[i] > 0) {
        lcp[ql[i]] = 0;
        for (int j = 0; j < ts[ql[i]].size() && j < ts[ql[i] - 1].size(); j++) {
          if (ts[ql[i]][j] != ts[ql[i] - 1][j]) break;
          lcp[ql[i]]++;
        }
      }
      if (ql[i] < n - 1) {
        lcp[ql[i] + 1] = 0;
        for (int j = 0; j < ts[ql[i]].size() && j < ts[ql[i] + 1].size(); j++) {
          if (ts[ql[i]][j] != ts[ql[i] + 1][j]) break;
          lcp[ql[i] + 1]++;
        }
      }
      if (lcp[ql[i]] >= LC && ql[i] > 0) {
        upd(ql[i], 1);
      } else if (ql[i] > 0) {
        upd(ql[i], 0);
      }
      if (lcp[ql[i] + 1] >= LC && ql[i] + 1 < n) {
        upd(ql[i] + 1, 1);
      } else if (ql[i] + 1 < n) {
        upd(ql[i] + 1, 0);
      }
    }
  }
  for (int i = 1; i <= q; i++) {
    if (qr[i]) {
      cout << ans[i] << endl;
    }
  }
}
