#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int BUBEN = (int)110;

struct Data {
  int goLeft[BUBEN], goRight[BUBEN];
  int res;
  int length;
  Data(int x) {
    x = min(x, BUBEN - 1);
    res = x;
    length = 1;
    for (int i = 0; i < BUBEN; i++) {
      if (i <= x) {
        goLeft[i] = goRight[i] = 1;
      } else {
        goLeft[i] = goRight[i] = 0;
      }
    }
  }
  Data() {}
};

void merge(const Data &l, const Data &r, Data &res) {
  res.res = max(l.res, r.res);
  res.length = l.length + r.length;
  for (int i = 0; i < BUBEN; i++) {
    res.goLeft[i] = l.goLeft[i];
    if (res.goLeft[i] == l.length) res.goLeft[i] += r.goLeft[i];
    res.goRight[i] = r.goRight[i];
    if (res.goRight[i] == r.length) res.goRight[i] += l.goRight[i];
    if (r.goLeft[i] || l.goRight[i]) {
      res.res = max(res.res, i * (r.goLeft[i] + l.goRight[i] + 1));
    }
  }
}

struct SegmentTree {
  Data *t;
  Data tmp, tmp2;
  int n;
  SegmentTree(int n) : n(n) {
    t = new Data[4 * n + 3];
  }
  SegmentTree() {}
  void change(int v, int tl, int tr, int pos, int val) {
    if (tl == tr) {
      t[v] = Data(val);
    } else {
      int tm = (tl + tr) >> 1;
      if (pos <= tm) {
        change(v + v, tl, tm, pos, val);
      } else {
        change(v + v + 1, tm + 1, tr, pos, val);
      }
      merge(t[v + v], t[v + v + 1], t[v]);
    }
  }
  void build(int v, int tl, int tr, int *a) {
    if (tl == tr) {
      t[v] = Data(a[tl]);
    } else {
      int tm = (tl + tr) >> 1;
      build(v + v, tl, tm, a);
      build(v + v + 1, tm + 1, tr, a);
      merge(t[v + v], t[v + v + 1], t[v]);
    }
  }
  void build(int *a) {
    build(1, 1, n, a);
  }
  void change(int pos, int val) {
    change(1, 1, n, pos, val);
  }
  void get(int v, int tl, int tr, int l, int r) {
    if (r < tl || l > tr) return;
    if (tl >= l && tr <= r) {
      merge(tmp, t[v], tmp2);
      memcpy(&tmp, &tmp2, sizeof(tmp));
    } else {
      int tm = (tl + tr) >> 1;
      get(v + v, tl, tm, l, r);
      get(v + v + 1, tm + 1, tr, l, r);
    }
  }
  int solve(int l, int r) {
    memset(&tmp, 0, sizeof(tmp));
    memset(&tmp2, 0, sizeof(tmp2));
    get(1, 1, n, l, r);
    return tmp.res;
  }
};


int solveHistogram(const vector<int> &a) {
  int n = (int)a.size();
  vector<int> gol(n), gor(n);
  vector<int> st;
  st.reserve(n);
  for (int i = 0; i < n; i++) {
    while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
    if (st.empty()) {
      gol[i] = 0;
    } else {
      gol[i] = st.back() + 1;
    }
    st.push_back(i);
  }
  st.clear();
  for (int i = n - 1; i >= 0; i--) {
    while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
    if (st.empty()) {
      gor[i] = n - 1;
    } else {
      gor[i] = st.back() - 1;
    }
    st.push_back(i);
  }
  int res = 0;
  for (int i = 0; i < n; i++) {
    res = max(res, a[i] * (gor[i] - gol[i] + 2));
  }
  return res;
}

struct LargeSolver {
  int *a;
  int n;
  set<int> largePoses;
  LargeSolver(int n) : n(n) {
    a = new int[n + 1];
  }
  LargeSolver() {}
  void change(int pos, int val) {
    if (a[pos] >= BUBEN) {
      largePoses.erase(pos);
    }
    a[pos] = val;
    if (a[pos] >= BUBEN) {
      largePoses.insert(pos);
    }
  }
  int solve(int l, int r) {
    auto it = largePoses.lower_bound(l);
    int res = 0;
    vector<int> cur;
    int lst = -1;
    while (it != largePoses.end() && (*it) <= r) {
      int curPos = (*it);
      if (curPos != lst + 1 && !cur.empty()) {
        res = max(res, solveHistogram(cur));
        cur.clear();
      }
      cur.push_back(a[curPos]);
      lst = curPos;
      it++;
    }
    if (!cur.empty()) {
      res = max(res, solveHistogram(cur));
    }
    return res;
  }
};

struct MaxSegmentTree {
  int *t;
  int n;
  MaxSegmentTree(int n) : n(n) {
    t = new int[4 * n + 3];
  }
  MaxSegmentTree() {}
  void change(int v, int tl, int tr, int pos, int val) {
    if (tl == tr) {
      t[v] = val;
    } else {
      int tm = (tl + tr) >> 1;
      if (pos <= tm) {
        change(v + v, tl, tm, pos, val);
      } else {
        change(v + v + 1, tm + 1, tr, pos, val);
      }
      t[v] = max(t[v + v], t[v + v + 1]);
    }
  }
  void change(int pos, int val) {
    change(1, 1, n, pos, val);
  }
  int getMax(int v, int tl, int tr, int l, int r) {
    if (r < tl || l > tr) return 0;
    if (tl >= l && tr <= r) return t[v];
    int tm = (tl + tr) >> 1;
    return max(getMax(v + v, tl, tm, l, r), getMax(v + v + 1, tm + 1, tr, l, r));
  }
  int getMax(int l, int r) {
    return getMax(1, 1, n, l, r);
  }
};

struct DynamicHystogramSolver {
  SegmentTree st;
  LargeSolver ls;
  DynamicHystogramSolver() {}
  DynamicHystogramSolver(int *a, int n) {
    st = SegmentTree(n);
    st.build(a);
    ls = LargeSolver(n);
    for (int i = 1; i <= n; i++) {
      ls.change(i, a[i]);
    }
  }
  void change(int pos, int val) {
    st.change(pos, val);
    ls.change(pos, val);
  }
  int getMax(int l, int r) {
    if (l > r) return 0;
    return max(st.solve(l, r), ls.solve(l, r));
  }
};

int getLCP(const string &s, const string &t) {
  int ptr = 0;
  while (ptr < (int)min(s.size(), t.size()) && s[ptr] == t[ptr]) ptr++;
  return ptr;
}
struct Solver {
  string *s;
  int *lcp;
  int n;
  DynamicHystogramSolver dhs;
  MaxSegmentTree st;
  Solver(const vector<string> &a) {
    n = a.size();
    s = new string[n + 1];
    lcp = new int[n + 1];
    for (int i = 1; i <= n; i++) {
      s[i] = a[i - 1];
    }
    for (int i = 1; i < n; i++) {
      lcp[i] = getLCP(s[i], s[i + 1]);
    }
    dhs = DynamicHystogramSolver(lcp, n);
    st = MaxSegmentTree(n);
    for (int i = 1; i <= n; i++) {
      st.change(i, (int)s[i].size());
    }
  }
  void change(int pos, const string &str) {
    s[pos] = str;
    if (pos != 1) {
      lcp[pos - 1] = getLCP(s[pos - 1], s[pos]);
      dhs.change(pos - 1, lcp[pos - 1]);
    }
    if (pos != n) {
      lcp[pos] = getLCP(s[pos], s[pos + 1]);
      dhs.change(pos, lcp[pos]);
    }
    st.change(pos, (int)str.size());
  }
  int solve(int l, int r) {
    return max(dhs.getMax(l, r - 1), st.getMax(l, r));
  }
};

const int MX = 300 * 1000 + 7;

char buf[MX];

string getString() {
  scanf("%s", buf);
  return string(buf);
}

int main() {
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  int n, q;
  scanf("%d %d", &n, &q);
  vector<string> s(n);
  for (int i = 0; i < n; i++) {
    s[i] = getString();
  }
  Solver solver(s);
  for (int i = 0; i < q; i++) {
    int type;
    scanf("%d", &type);
    if (type == 1) {
      int l, r;
      scanf("%d %d", &l, &r);
      printf("%d\n", solver.solve(l, r));
    } else {
      int pos;
      scanf("%d ", &pos);
      solver.change(pos, getString());
    }
  }
  return 0;
}