#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int ch[maxn][26];
int root, tot;
int dfn[maxn * 2], in[maxn], idx = 0, dep[maxn];
void dfs(int u) {
  dfn[in[u] = ++idx] = u;
  for (int i = (0); i < (26); ++i) {
    if (ch[u][i] == 0) continue;
    dep[ch[u][i]] = dep[u] + 1;
    dfs(ch[u][i]);
    dfn[++idx] = u;
  }
}
int Min(int x, int y) { return (dep[x] < dep[y]) ? x : y; }
int f[maxn * 2][20];
int lg2[maxn * 2];
int lca(int x, int y) {
  x = in[x], y = in[y];
  if (x > y) swap(x, y);
  int k = lg2[y - x + 1];
  return Min(f[x][k], f[y - (1 << k) + 1][k]);
}
void init_lca() {
  lg2[0] = -1;
  for (int i = (1); i < (idx + 1); ++i)
    f[i][0] = dfn[i], lg2[i] = lg2[i >> 1] + 1;
  for (int j = 1; j < 19; ++j) {
    for (int i = 1; i + (1 << j) - 1 <= idx; ++i)
      f[i][j] = Min(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
  }
}
int ip[maxn];
int n, m;
int op[maxn], a[maxn], b[maxn];
char s[maxn];
void init() {
  root = tot = 1;
  cin >> n >> m;
  for (int i = (1); i < (n + 1); ++i) {
    scanf("%s", s);
    int len = strlen(s);
    int p = root;
    for (int j = (0); j < (len); ++j) {
      int x = s[j] - 'a';
      if (!ch[p][x]) ch[p][x] = ++tot;
      p = ch[p][x];
    }
    ip[i] = p;
  }
  for (int i = (1); i < (m + 1); ++i) {
    scanf("%d", &op[i]);
    if (op[i] == 1)
      scanf("%d%d", &a[i], &b[i]);
    else {
      scanf("%d", &a[i]);
      scanf("%s", s);
      int len = strlen(s);
      int p = root;
      for (int j = (0); j < (len); ++j) {
        int x = s[j] - 'a';
        if (!ch[p][x]) ch[p][x] = ++tot;
        p = ch[p][x];
      }
      b[i] = p;
    }
  }
  dfs(root);
  init_lca();
}
struct node {
  vector<pair<int, int> > f, g;
  int ans;
  node() {
    f.clear();
    g.clear();
    ans = 0;
  }
} t[maxn << 2];
node merge(node a, node b) {
  node tmp;
  tmp.f = a.f;
  for (int i = (0); i < (b.f.size()); ++i) {
    int u = b.f[i].first;
    int id = b.f[i].second;
    assert(tmp.f.size());
    int pre = tmp.f[tmp.f.size() - 1].first;
    int p = lca(u, pre);
    if (p != pre)
      tmp.f.push_back(pair<int, int>(p, id));
    else
      tmp.f[tmp.f.size() - 1].second = id;
  }
  tmp.g = b.g;
  for (int i = (0); i < (a.g.size()); ++i) {
    int u = a.g[i].first;
    int id = a.g[i].second;
    assert(tmp.g.size());
    int pre = tmp.g[tmp.g.size() - 1].first;
    int p = lca(u, pre);
    if (p != pre)
      tmp.g.push_back(pair<int, int>(p, id));
    else
      tmp.g[tmp.g.size() - 1].second = id;
  }
  tmp.ans = max(a.ans, b.ans);
  int rp = 0;
  for (int i = (0); i < (a.g.size()); ++i) {
    int u = a.g[i].first;
    int id1 = a.g[i].second;
    while (rp + 1 < b.f.size()) {
      int v1 = b.f[rp].first;
      int v2 = b.f[rp + 1].first;
      int p1 = lca(u, v1);
      int p2 = lca(u, v2);
      if (dep[p1] <= dep[p2])
        rp++;
      else
        break;
    }
    int v = b.f[rp].first;
    int id2 = b.f[rp].second;
    int p = lca(u, v);
    tmp.ans = max(tmp.ans, (id2 - id1 + 1) * dep[p]);
  }
  int lp = 0;
  for (int i = (0); i < (b.f.size()); ++i) {
    int v = b.f[i].first;
    int id2 = b.f[i].second;
    while (lp + 1 < a.g.size()) {
      int u1 = a.g[lp].first;
      int u2 = a.g[lp + 1].first;
      int p1 = lca(v, u1);
      int p2 = lca(v, u2);
      if (dep[p1] <= dep[p2])
        lp++;
      else
        break;
    }
    int u = a.g[lp].first;
    int id1 = a.g[lp].second;
    int p = lca(u, v);
    tmp.ans = max(tmp.ans, (id2 - id1 + 1) * dep[p]);
  }
  return tmp;
}
void build(int rt, int l, int r) {
  if (l == r) {
    t[rt].f.push_back(pair<int, int>(ip[l], l));
    t[rt].g.push_back(pair<int, int>(ip[l], l));
    t[rt].ans = dep[ip[l]];
    return;
  }
  build(rt << 1, l, ((l + r) >> 1));
  build(rt << 1 | 1, ((l + r) >> 1) + 1, r);
  t[rt] = merge(t[rt << 1], t[rt << 1 | 1]);
  return;
}
void update(int rt, int l, int r, int pos, int x) {
  if (l == r) {
    t[rt].f.clear();
    t[rt].f.push_back(pair<int, int>(x, l));
    t[rt].g.clear();
    t[rt].g.push_back(pair<int, int>(x, l));
    t[rt].ans = dep[x];
    return;
  }
  if (pos <= ((l + r) >> 1))
    update(rt << 1, l, ((l + r) >> 1), pos, x);
  else
    update(rt << 1 | 1, ((l + r) >> 1) + 1, r, pos, x);
  t[rt] = merge(t[rt << 1], t[rt << 1 | 1]);
  return;
}
node qry(int rt, int l, int r, int L, int R) {
  if (L <= l && r <= R) {
    return t[rt];
  }
  if (L <= ((l + r) >> 1) && R > ((l + r) >> 1)) {
    return merge(qry(rt << 1, l, ((l + r) >> 1), L, R),
                 qry(rt << 1 | 1, ((l + r) >> 1) + 1, r, L, R));
  } else if (L <= ((l + r) >> 1))
    return qry(rt << 1, l, ((l + r) >> 1), L, R);
  else
    return qry(rt << 1 | 1, ((l + r) >> 1) + 1, r, L, R);
}
void sol() {
  build(1, 1, n);
  for (int i = (1); i < (m + 1); ++i) {
    if (op[i] == 1) {
      node tmp = qry(1, 1, n, a[i], b[i]);
      printf("%d\n", tmp.ans);
    } else {
      update(1, 1, n, a[i], b[i]);
    }
  }
}
int main() {
  init();
  sol();
  return 0;
}
