#include <bits/stdc++.h>
#pragma GCC target("pclmul")
using ul = std::uint32_t;
using ull = std::uint64_t;
using li = std::int32_t;
using ll = std::int64_t;
using llf = long double;
using us = std::uint16_t;
const ul maxn = 1e5;
const ul maxlen = 1e5;
const ul bu = 30;
std::mt19937_64 rnd;
class node {
 public:
  ul lc = 0;
  ul rc = 0;
  ul val = 0;
  ul ans[bu + 1];
  ul lenl[bu + 1];
  ul lenr[bu + 1];
  ul cnt = 0;
  ull rk = 0;
};
ul tim;
node tree[maxn + maxn];
void update(ul x) {
  tree[x].cnt = tree[tree[x].lc].cnt + tree[tree[x].rc].cnt + 1;
  for (ul i = 1; i <= bu; ++i) {
    ul tmp = tree[x].val >= i;
    if (tmp) {
      tmp += tree[tree[x].lc].lenr[i] + tree[tree[x].rc].lenl[i];
    }
    tree[x].ans[i] = std::max(
        tmp, std::max(tree[tree[x].lc].ans[i], tree[tree[x].rc].ans[i]));
    tree[x].lenl[i] = tree[tree[x].lc].lenr[i] == tree[tree[x].lc].cnt && tmp
                          ? tmp
                          : tree[tree[x].lc].lenl[i];
    tree[x].lenr[i] = tree[tree[x].rc].lenl[i] == tree[tree[x].rc].cnt && tmp
                          ? tmp
                          : tree[tree[x].rc].lenr[i];
  }
}
void split(ul x, ul& a, ul& b, ul key) {
  if (!x) {
    a = b = 0;
    return;
  }
  if (x < key) {
    a = x;
    split(tree[x].rc, tree[a].rc, b, key);
  } else {
    b = x;
    split(tree[x].lc, a, tree[b].lc, key);
  }
  update(x);
}
void merge(ul& x, ul a, ul b) {
  if (!a || !b) {
    x = a ^ b;
    return;
  }
  if (tree[a].rk > tree[b].rk) {
    x = a;
    merge(tree[x].rc, tree[a].rc, b);
  } else {
    x = b;
    merge(tree[x].lc, a, tree[b].lc);
  }
  update(x);
}
ul n;
ul q;
std::string s[maxn + 1];
char str[maxlen + 2];
ul root;
ul lcp(const std::string& a, const std::string& b) {
  ul i = 0;
  for (; i != a.size() && i != b.size() && a[i] == b[i]; ++i)
    ;
  return i;
}
ul sz = 0;
std::pair<ul, ul> stack[maxn + maxn];
ul left[maxn + maxn];
ul right[maxn + maxn];
std::vector<std::pair<ul, ul>> stack2;
bool al = false;
void erase(ul key) {
  --sz;
  for (ul i = 1; i <= sz; ++i) {
    if (stack[i].first >= key) {
      stack[i] = stack[i + 1];
    }
  }
  al = false;
}
void insert(ul key, ul val) {
  ++sz;
  for (ul i = sz; i >= 1; --i) {
    if (stack[i - 1].first > key) {
      stack[i] = stack[i - 1];
    } else {
      stack[i].first = key;
      stack[i].second = val;
      break;
    }
  }
  al = false;
}
int main() {
  rnd.seed(std::time(0));
  std::scanf("%u%u", &n, &q);
  for (ul i = 1; i <= n; ++i) {
    std::scanf("%s", str + 1);
    s[i] = str + 1;
    if (i != 1) {
      ++tim;
      tree[tim].val = lcp(s[i - 1], s[i]);
      tree[tim].rk = rnd();
      update(tim);
      merge(root, root, tim);
      if (tree[tim].val > bu) {
        ++sz;
        stack[sz].first = tim;
        stack[sz].second = tree[tim].val;
      }
    }
    ++tim;
    tree[tim].val = s[i].size();
    tree[tim].rk = rnd();
    update(tim);
    merge(root, root, tim);
    if (tree[tim].val > bu) {
      ++sz;
      stack[sz].first = tim;
      stack[sz].second = tree[tim].val;
    }
  }
  for (ul Case = 1; Case <= q; ++Case) {
    ul k;
    std::scanf("%u", &k);
    if (k == 1) {
      ul x, y;
      std::scanf("%u%u", &x, &y);
      x = (x << 1) - 1;
      y = (y << 1) - 1;
      ul a, b, c;
      split(root, a, b, x);
      split(b, b, c, y + 1);
      ul ans = 0;
      for (ul i = 1; i <= bu; ++i) {
        ans = std::max(ans, (tree[b].ans[i] + 1 >> 1) * i);
      }
      merge(root, a, b);
      merge(root, root, c);
      if (!al) {
        al = true;
        for (ul i = 1; i <= sz; ++i) {
          if (i == 1 || stack[i].first != stack[i - 1].first + 1) {
            stack2.resize(0);
            stack2.push_back(std::pair<ul, ul>(stack[i].first - 1, 0));
          } else {
            while (stack2.size() && stack2.back().second >= stack[i].second) {
              stack2.pop_back();
            }
          }
          left[stack[i].first] = stack2.back().first + 1;
          stack2.push_back(stack[i]);
        }
        for (ul i = sz; i >= 1; --i) {
          if (i == sz || stack[i].first != stack[i + 1].first - 1) {
            stack2.resize(0);
            stack2.push_back(std::pair<ul, ul>(stack[i].first + 1, 0));
          } else {
            while (stack2.size() && stack2.back().second >= stack[i].second) {
              stack2.pop_back();
            }
          }
          right[stack[i].first] = stack2.back().first - 1;
          stack2.push_back(stack[i]);
        }
      }
      for (ul i = 1; i <= sz; ++i) {
        if (stack[i].first >= x && stack[i].first <= y) {
          ans = std::max(ans, (std::min(right[stack[i].first], y) -
                                   std::max(left[stack[i].first], x) + 1 + 1 >>
                               1) *
                                  stack[i].second);
        }
      }
      std::printf("%u\n", ans);
    } else {
      ul x;
      std::scanf("%u%s", &x, str + 1);
      s[x] = str + 1;
      ul y = (x << 1) - 1;
      ul a, b, c;
      split(root, a, b, std::max(y - 1, ul(1)));
      split(b, b, c, std::min(y + 1, n + n - 1) + 1);
      if (tree[y].val > bu) {
        erase(y);
      }
      tree[y].val = s[x].size();
      tree[y].lc = 0;
      tree[y].rc = 0;
      update(y);
      if (tree[y].val > bu) {
        insert(y, tree[y].val);
      }
      b = y;
      if (x != 1) {
        if (tree[y - 1].val > bu) {
          erase(y - 1);
        }
        tree[y - 1].val = lcp(s[x - 1], s[x]);
        tree[y - 1].lc = 0;
        tree[y - 1].rc = 0;
        update(y - 1);
        if (tree[y - 1].val > bu) {
          insert(y - 1, tree[y - 1].val);
        }
        merge(b, y - 1, b);
      }
      if (x != n) {
        if (tree[y + 1].val > bu) {
          erase(y + 1);
        }
        tree[y + 1].val = lcp(s[x], s[x + 1]);
        tree[y + 1].lc = 0;
        tree[y + 1].rc = 0;
        update(y + 1);
        if (tree[y + 1].val > bu) {
          insert(y + 1, tree[y + 1].val);
        }
        merge(b, b, y + 1);
      }
      merge(b, a, b);
      merge(b, b, c);
      root = b;
    }
  }
  return 0;
}
