#include <bits/stdc++.h>
#pragma warning(disable : 4996)
template <typename T>
T min(T x, T y) {
  return x < y ? x : y;
}
template <typename T>
T max(T x, T y) {
  return x > y ? x : y;
};
const int MAXN = 100005;
struct tree1 {
 private:
  int mx;
  int l;
  int r;
  tree1 *lson;
  tree1 *rson;

 public:
  tree1() {
    mx = 0;
    lson = rson = NULL;
  }
  void build(int L, int R) {
    l = L;
    r = R;
    if (l == r) return;
    lson = new tree1;
    rson = new tree1;
    int mid = (l + r) / 2;
    lson->build(l, mid);
    rson->build(mid + 1, r);
  }
  void modify(int id, int k) {
    if (l == r) {
      mx = k;
      return;
    }
    int mid = (l + r) / 2;
    if (id <= mid)
      lson->modify(id, k);
    else
      rson->modify(id, k);
    mx = max(lson->mx, rson->mx);
  }
  int query(int L, int R) {
    if (l >= L && r <= R) return mx;
    int mid = (l + r) / 2;
    if (R <= mid) return lson->query(L, R);
    if (L > mid) return rson->query(L, R);
    return max(lson->query(L, R), rson->query(L, R));
  }
};
struct line {
  int k;
  int b;
  line(int K = 0, int B = 0) {
    k = K;
    b = B;
  }
  int calc(int x) { return k * x + b; }
  double cross(line t) { return (double)(t.b - b) / (k - t.k); }
};
struct tree {
  bool tag;
  int l;
  int r;
  line *L;
  int cnt;
  line *R;
  int rcnt;
  int mx;
  tree *lson;
  tree *rson;
  tree() {
    tag = false;
    L = R = NULL;
    cnt = rcnt = mx = 0;
    lson = rson = NULL;
  }
  void fixup() {
    static line tmp[MAXN];
    l = lson->l;
    r = rson->r;
    if (L) delete L;
    L = new line[lson->cnt + rson->cnt];
    cnt = lson->cnt;
    for (int i = 0; i < cnt; i++) L[i] = lson->L[i];
    for (int i = 0; i < rson->cnt; i++) {
      if (rson->L[i].k >= L[cnt - 1].k)
        L[cnt - 1].b = (lson->r - lson->l + 1) + rson->L[i].b;
      else {
        L[cnt++] = rson->L[i];
        L[cnt - 1].b += (lson->r - lson->l + 1);
      }
    }
    if (R) delete R;
    R = new line[lson->rcnt + rson->rcnt];
    rcnt = rson->rcnt;
    for (int i = 0; i < rcnt; i++) R[i] = rson->R[i];
    for (int i = 0; i < lson->rcnt; i++) {
      if (lson->R[i].k >= R[rcnt - 1].k)
        R[rcnt - 1].b = (rson->r - rson->l + 1) + lson->R[i].b;
      else {
        R[rcnt++] = lson->R[i];
        R[rcnt - 1].b += (rson->r - rson->l + 1);
      }
    }
    mx = max(lson->mx, rson->mx);
    int cur = 0, p = 0, s = 0;
    memset(tmp, 0, sizeof(line) * rson->cnt);
    std::reverse(lson->R, lson->R + lson->rcnt);
    std::reverse(rson->L, rson->L + rson->cnt);
    for (int i = 0; i < lson->rcnt; i++) {
      while (cur < rson->cnt && rson->L[cur].k < lson->R[i].k) {
        line t = rson->L[cur++];
        t.b = (t.b + 1) * t.k;
        while (s > 1 && tmp[s - 2].cross(t) < tmp[s - 2].cross(tmp[s - 1])) s--;
        if (p >= s) p = max(s - 1, 0);
        tmp[s++] = t;
      }
      while (p < s - 1 &&
             tmp[p].calc(lson->R[i].b) < tmp[p + 1].calc(lson->R[i].b))
        p++;
      while (p && tmp[p].calc(lson->R[i].b) < tmp[p - 1].calc(lson->R[i].b))
        p--;
      if (cur < rson->cnt)
        mx = max(mx, (lson->R[i].b + rson->L[cur].b + 1) * lson->R[i].k);
      mx = max(mx, tmp[p].calc(lson->R[i].b));
    }
    std::reverse(lson->R, lson->R + lson->rcnt);
    std::reverse(rson->L, rson->L + rson->cnt);
  }
  void build(int rL, int rR, int *a) {
    tag = true;
    l = rL;
    r = rR;
    if (l == r) {
      mx = a[l] * 2;
      L = new line[1];
      R = new line[1];
      cnt = rcnt = 1;
      L[0] = R[0] = line(a[l], 1);
      return;
    }
    int mid = (l + r) / 2;
    lson = new tree;
    rson = new tree;
    lson->build(l, mid, a);
    rson->build(mid + 1, r, a);
    fixup();
  }
  void modify(int id, int k) {
    if (l == r) {
      mx = k * 2;
      L[0] = R[0] = line(k, 1);
      return;
    }
    int mid = (l + r) / 2;
    if (id <= mid)
      lson->modify(id, k);
    else
      rson->modify(id, k);
    fixup();
  }
  tree *query(int rL, int rR) {
    if (l >= rL && r <= rR) return this;
    int mid = (l + r) / 2;
    if (rR <= mid) return lson->query(rL, rR);
    if (rL > mid) return rson->query(rL, rR);
    tree *temp = new tree;
    temp->lson = lson->query(rL, rR);
    temp->rson = rson->query(rL, rR);
    temp->fixup();
    return temp;
  }
  void query_clear() {
    if (tag) return;
    lson->query_clear();
    rson->query_clear();
    if (L) delete L;
    if (R) delete R;
  }
};
void print(int *a, int n) {
  for (int i = 1; i <= n; i++) printf("%d ", a[i]);
  printf("\n");
}
int N, q;
tree1 T1;
tree T;
char *s[MAXN], str[MAXN];
int len[MAXN], lcp[MAXN];
void init() {
  scanf("%d %d", &N, &q);
  T1.build(1, N);
  for (int i = 1; i <= N; i++) {
    scanf("%s", str);
    len[i] = strlen(str);
    s[i] = new char[len[i]];
    memcpy(s[i], str, sizeof(char) * len[i]);
    T1.modify(i, len[i]);
  }
  for (int i = 1; i < N; i++) {
    int t = 0;
    while (t < len[i] && t < len[i + 1] && s[i][t] == s[i + 1][t]) t++;
    lcp[i] = t;
  }
  if (N > 1) T.build(1, N - 1, lcp);
}
int main() {
  int ty, x, y;
  init();
  for (int i = 0; i < q; i++) {
    scanf("%d %d", &ty, &x);
    if (ty == 1) {
      scanf("%d", &y);
      int ans = T1.query(x, y);
      if (x == y) {
        printf("%d\n", ans);
        continue;
      }
      tree *p = T.query(x, y - 1);
      ans = max(ans, p->mx);
      p->query_clear();
      if (!p->l && !p->r) delete p;
      std::cout << ans << std::endl;
    } else {
      scanf("%s", str);
      len[x] = strlen(str);
      s[x] = new char[len[x]];
      memcpy(s[x], str, sizeof(char) * len[x]);
      T1.modify(x, len[x]);
      int t = 0;
      if (x > 1) {
        for (t = 0; t < len[x - 1] && t < len[x] && s[x - 1][t] == s[x][t]; t++)
          ;
        lcp[x - 1] = t;
        T.modify(x - 1, t);
      }
      if (x < N) {
        for (t = 0; t < len[x] && t < len[x + 1] && s[x][t] == s[x + 1][t]; t++)
          ;
        lcp[x] = t;
        T.modify(x, t);
      }
    }
  }
  return 0;
}
