#include <bits/stdc++.h>
using namespace std;
const int MAX = 1e5 + 5;
const int SQ = 80;
int n, q;
string s[MAX];
int lcp[MAX];
set<int> active;
const int LIM = 3e5 + 5;
struct node {
  int lsuf[SQ], rsuf[SQ], maxi, len;
  node() {
    maxi = len = 0;
    for (int i = 0; i < SQ; i++) {
      lsuf[i] = rsuf[i] = 0;
    }
  }
  node(int x) {
    x = min(SQ - 1, x);
    maxi = x;
    len = 1;
    for (int i = 0; i < SQ; i++) {
      lsuf[i] = rsuf[i] = (i <= x);
    }
  }
  node operator+(const node& other) {
    node res;
    res.maxi = max(other.maxi, maxi);
    res.len = other.len + len;
    for (int i = 0; i < SQ; i++) {
      res.lsuf[i] = lsuf[i];
      if (len == lsuf[i]) {
        res.lsuf[i] += other.lsuf[i];
      }
      res.rsuf[i] = other.rsuf[i];
      if (other.rsuf[i] == other.len) {
        res.rsuf[i] += rsuf[i];
      }
      if (rsuf[i] || other.lsuf[i]) {
        res.maxi = max(res.maxi, i * (rsuf[i] + other.lsuf[i] + 1));
      }
    }
    return res;
  }
} segt[LIM];
int seg[LIM];
void combine(int t) { seg[t] = max(seg[t * 2], seg[t * 2 + 1]); }
void build(int t, int i, int j) {
  if (i == j) {
    seg[t] = s[i].length();
    return;
  }
  int mid = (i + j) / 2;
  build(t * 2, i, mid);
  build(t * 2 + 1, mid + 1, j);
  combine(t);
}
void update(int t, int i, int j, int x) {
  if (i > x || j < x) {
    return;
  }
  if (i == j) {
    seg[t] = s[i].length();
    return;
  }
  int mid = (i + j) / 2;
  update(t * 2, i, mid, x);
  update(t * 2 + 1, mid + 1, j, x);
  combine(t);
}
int query(int t, int i, int j, int l, int r) {
  if (i > r || j < l) {
    return 0;
  }
  if (l <= i && j <= r) {
    return seg[t];
  }
  int mid = (i + j) / 2;
  int a = query(t * 2, i, mid, l, r);
  int b = query(t * 2 + 1, mid + 1, j, l, r);
  return max(a, b);
}
void combine2(int t) { segt[t] = segt[t * 2] + segt[t * 2 + 1]; }
void build2(int t, int i, int j) {
  if (i == j) {
    segt[t] = node(lcp[i]);
    return;
  }
  int mid = (i + j) / 2;
  build2(t * 2, i, mid);
  build2(t * 2 + 1, mid + 1, j);
  combine2(t);
}
void update2(int t, int i, int j, int x) {
  if (i > x || j < x) {
    return;
  }
  if (i == j) {
    segt[t] = node(lcp[i]);
    return;
  }
  int mid = (i + j) / 2;
  update2(t * 2, i, mid, x);
  update2(t * 2 + 1, mid + 1, j, x);
  combine2(t);
}
node query2(int t, int i, int j, int l, int r) {
  if (i > r || j < l) {
    return node(0);
  }
  if (l <= i && j <= r) {
    return segt[t];
  }
  int mid = (i + j) / 2;
  node a = query2(t * 2, i, mid, l, r);
  node b = query2(t * 2 + 1, mid + 1, j, l, r);
  return (a + b);
}
int lc(int x, int y) {
  int ptr = 0;
  while (ptr < s[x].length() && ptr < s[y].length() && s[x][ptr] == s[y][ptr]) {
    ptr++;
  }
  return ptr;
}
int solve1(int a, int b) {
  b--;
  if (a > b) {
    return s[a].length();
  }
  int an = query2(1, 1, n - 1, a, b).maxi;
  b++;
  an = max(an, query(1, 1, n, a, b));
  return an;
}
vector<int> tmp;
int rgt[2 * MAX];
int lft[2 * MAX];
stack<int> st;
int solve2(int a, int b) {
  b--;
  if (a > b) {
    return s[a].length();
  }
  set<int>::iterator it = active.lower_bound(a);
  set<int>::iterator it1 = active.upper_bound(b);
  int last = -1;
  for (; it != it1; it++) {
    if ((*it) != (last + 1)) {
      tmp.push_back(0);
    }
    tmp.push_back(lcp[*it]);
    last = (*it);
  }
  for (int i = 0; i < tmp.size(); i++) {
    while (st.size() > 0 && tmp[st.top()] >= tmp[i]) {
      st.pop();
    }
    if (!st.size()) {
      lft[i] = -1;
    } else {
      lft[i] = st.top();
    }
    st.push(i);
  }
  while (!st.empty()) {
    st.pop();
  }
  for (int i = tmp.size() - 1; i >= 0; i--) {
    int u = tmp[i];
    while (st.size() > 0 && tmp[st.top()] >= tmp[i]) {
      st.pop();
    }
    if (!st.size()) {
      rgt[i] = tmp.size();
    } else {
      rgt[i] = st.top();
    }
    st.push(i);
  }
  while (!st.empty()) {
    st.pop();
  }
  int ans = 0;
  for (int i = 0; i < tmp.size(); i++) {
    int u = tmp[i];
    ans = max(ans, u * (rgt[i] - lft[i]));
  }
  tmp.clear();
  return ans;
}
int main() {
  scanf("%d %d", &n, &q);
  for (int i = 1; i <= n; i++) {
    cin >> s[i];
  }
  for (int i = 1; i < n; i++) {
    lcp[i] = lc(i, i + 1);
  }
  build(1, 1, n);
  if (n > 1) build2(1, 1, n - 1);
  for (int i = 1; i < n; i++) {
    if (lcp[i] >= SQ) {
      active.insert(i);
    }
  }
  for (int i = 1; i <= q; i++) {
    int typ;
    scanf("%d", &typ);
    if (typ == 1) {
      int a, b;
      scanf("%d %d", &a, &b);
      printf("%d\n", max(solve1(a, b), solve2(a, b)));
    } else {
      int a;
      string b;
      scanf("%d", &a);
      cin >> b;
      s[a] = b;
      update(1, 1, n, a);
      if (a < n) {
        if (lcp[a] >= SQ) {
          active.erase(a);
        }
        lcp[a] = lc(a, a + 1);
        if (lcp[a] >= SQ) {
          active.insert(a);
        }
        update2(1, 1, n - 1, a);
      }
      if (a > 1) {
        if (lcp[a - 1] >= SQ) {
          active.erase(a - 1);
        }
        lcp[a - 1] = lc(a - 1, a);
        if (lcp[a - 1] >= SQ) {
          active.insert(a - 1);
        }
        update2(1, 1, n - 1, a - 1);
      }
    }
  }
  return 0;
}
