#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int SIZE = 1 << 17;
string s[SIZE];
int h[SIZE];
int ma[SIZE * 2 + 100];
vector<pair<int, int> > stkL[SIZE * 2 + 100], stkR[SIZE * 2 + 100];
void pre(int n) {
  for (int i = (2); i < (n + 1); ++i) {
    while (h[i] < min(((int)(s[i - 1]).size()), ((int)(s[i]).size())) &&
           s[i - 1][h[i]] == s[i][h[i]])
      h[i]++;
  }
}
int sid;
void pull(int id, int mm_v, int idL = 0, int idR = 0) {
  if (idL == 0) idL = id * 2;
  if (idR == 0) idR = id * 2 + 1;
  ma[id] = max(ma[idL], ma[idR]);
  int itR = 0, itL = 0;
  int num = 0;
  while (itR < ((int)(stkR[idL]).size()) && stkR[idL][itR].first >= mm_v)
    num += stkR[idL][itR++].second;
  while (itL < ((int)(stkL[idR]).size()) && stkL[idR][itL].first >= mm_v)
    num += stkL[idR][itL++].second;
  ma[id] = max(ma[id], num * mm_v);
  while (itR < ((int)(stkR[idL]).size()) && itL < ((int)(stkL[idR]).size())) {
    if (stkR[idL][itR] >= stkL[idR][itL]) {
      num += stkR[idL][itR].second;
      ma[id] = max(ma[id], num * stkR[idL][itR++].first);
    } else {
      num += stkL[idR][itL].second;
      ma[id] = max(ma[id], num * stkL[idR][itL++].first);
    }
  }
  while (itR < ((int)(stkR[idL]).size())) {
    num += stkR[idL][itR].second;
    ma[id] = max(ma[id], num * stkR[idL][itR++].first);
  }
  while (itL < ((int)(stkL[idR]).size())) {
    num += stkL[idR][itL].second;
    ma[id] = max(ma[id], num * stkL[idR][itL++].first);
  }
  stkL[id] = stkL[idL];
  stkL[id].resize(((int)(stkL[idL]).size()) + ((int)(stkL[idR]).size()));
  itL = ((int)(stkL[idL]).size());
  int now_v = min(stkL[idL].back().first, mm_v);
  int it = 0;
  int sp_num = 0;
  while (it < ((int)(stkL[idR]).size()) && stkL[idR][it].first >= now_v) {
    sp_num += stkL[idR][it++].second;
  }
  if (sp_num) {
    if (now_v == stkL[idL].back().first) {
      stkL[id][((int)(stkL[idL]).size()) - 1].second += sp_num;
    } else {
      stkL[id][itL++] = make_pair(now_v, sp_num);
    }
    sp_num = 0;
  }
  for (; it < ((int)(stkL[idR]).size()); it++) stkL[id][itL++] = stkL[idR][it];
  stkL[id].resize(itL);
  stkR[id] = stkR[idR];
  stkR[id].resize(((int)(stkR[idL]).size()) + ((int)(stkR[idR]).size()));
  itR = ((int)(stkR[idR]).size());
  now_v = min(stkR[idR].back().first, mm_v);
  it = 0;
  while (it < ((int)(stkR[idL]).size()) && stkR[idL][it].first >= now_v) {
    sp_num += stkR[idL][it++].second;
  }
  if (sp_num) {
    if (now_v == stkR[idR].back().first) {
      stkR[id][((int)(stkR[idR]).size()) - 1].second += sp_num;
    } else {
      stkR[id][itR++] = make_pair(now_v, sp_num);
    }
    sp_num = 0;
  }
  for (; it < ((int)(stkR[idL]).size()); it++) stkR[id][itR++] = stkR[idL][it];
  stkR[id].resize(itR);
}
void build(int L, int R, int id) {
  int mm = (L + R) / 2;
  if (L == R) {
    ma[id] = ((int)(s[L]).size());
    stkL[id] = stkR[id] = vector<pair<int, int> >(1, make_pair(ma[id], 1));
    return;
  }
  build(L, mm, id * 2);
  build(mm + 1, R, id * 2 + 1);
  pull(id, h[mm + 1]);
}
void print(string name, vector<pair<int, int> >& x) {
  printf("[%s:", name.c_str());
  for (int i = 0; i < (((int)(x).size())); ++i)
    printf("(%d,%d)%c", x[i].first, x[i].second,
           ",]"[i == ((int)(x).size()) - 1]);
  puts("");
}
int qq(int L, int R, int id, int ll, int rr, int rid) {
  if (R < ll || L > rr) {
    stkL[rid] = stkR[rid] = vector<pair<int, int> >();
    ma[rid] = 0;
    return 0;
  }
  if (L >= ll && R <= rr) {
    stkR[rid] = stkR[id];
    stkL[rid] = stkL[id];
    ma[rid] = ma[id];
    return ma[id];
  }
  int mm = (L + R) / 2;
  if (rr <= mm) return qq(L, mm, id * 2, ll, rr, rid);
  if (ll > mm) return qq(mm + 1, R, id * 2 + 1, ll, rr, rid);
  int ridL = sid++;
  int ridR = sid++;
  int ret = max(qq(L, mm, id * 2, ll, rr, ridL),
                qq(mm + 1, R, id * 2 + 1, ll, rr, ridR));
  pull(rid, h[mm + 1], ridL, ridR);
  ret = max(ret, ma[rid]);
  return ret;
}
void edit(int L, int R, int id, int x) {
  if (L == R) {
    ma[id] = ((int)(s[L]).size());
    stkL[id] = stkR[id] = vector<pair<int, int> >(1, make_pair(ma[id], 1));
    return;
  }
  int mm = (L + R) / 2;
  if (x <= mm)
    edit(L, mm, id * 2, x);
  else
    edit(mm + 1, R, id * 2 + 1, x);
  pull(id, h[mm + 1]);
}
void update(int x, int n) {
  cin >> s[x];
  for (int i = (max(2, x)); i < (min(x + 1, n) + 1); ++i) {
    h[i] = 0;
    while (h[i] < min(((int)(s[i - 1]).size()), ((int)(s[i]).size())) &&
           s[i - 1][h[i]] == s[i][h[i]])
      h[i]++;
  }
  edit(1, n, 1, x);
}
int main() {
  int n, q;
  scanf("%d%d", &n, &q);
  for (int i = (1); i < (n + 1); ++i) cin >> s[i];
  pre(n);
  build(1, n, 1);
  for (int ker = 0; ker < (q); ++ker) {
    int(ty);
    scanf("%d", &ty);
    if (ty == 1) {
      int x, y;
      scanf("%d%d", &x, &y);
      sid = SIZE * 2;
      printf("%d\n", qq(1, n, 1, x, y, sid++));
    } else {
      int(x);
      scanf("%d", &x);
      update(x, n);
    }
  }
  return 0;
}
