#include <bits/stdc++.h>
using namespace std;
struct vertex {
  map<char, int> next, go;
  int p, link;
  char pch;
  vector<int> leaf;
  vertex(int p = -1, char pch = -1) : p(p), link(-1), pch(pch) {}
};
vector<vertex> t;
void aho_init() {
  t.clear();
  t.push_back(vertex());
}
multiset<int> vals[300010];
vector<int> nodeOfId;
void add_string(string s, int id) {
  int v = 0;
  for (char c : s) {
    if (!t[v].next.count(c)) {
      t[v].next[c] = t.size();
      t.push_back(vertex(v, c));
    }
    v = t[v].next[c];
  }
  t[v].leaf.push_back(id);
  vals[v].insert(0);
  nodeOfId[id] = v;
}
int go(int v, char c);
int get_link(int v) {
  if (t[v].link < 0)
    if (!v || !t[v].p)
      t[v].link = 0;
    else
      t[v].link = go(get_link(t[v].p), t[v].pch);
  return t[v].link;
}
int go(int v, char c) {
  if (!t[v].go.count(c))
    if (t[v].next.count(c))
      t[v].go[c] = t[v].next[c];
    else
      t[v].go[c] = v == 0 ? 0 : go(get_link(v), c);
  return t[v].go[c];
}
const int neutro = -1;
struct RMQ {
  int sz;
  int t[4 * 300010];
  int& operator[](int p) { return t[sz + p]; }
  void init(int n) {
    sz = 1 << (32 - __builtin_clz(n));
    for (int i = (0); i < (2 * sz); i++) t[i] = neutro;
  }
  void updall() {
    for (int i = sz - 1; i >= 0; i--) t[i] = max(t[2 * i], t[2 * i + 1]);
  }
  int get(int i, int j) { return get(i, j, 1, 0, sz); }
  int get(int i, int j, int n, int a, int b) {
    if (j <= a || i >= b) return neutro;
    if (i <= a && b <= j) return t[n];
    int c = (a + b) / 2;
    return max(get(i, j, 2 * n, a, c), get(i, j, 2 * n + 1, c, b));
  }
  void set(int p, int val) {
    p += sz;
    while (p > 0 && t[p] != val) {
      t[p] = val;
      p /= 2;
      val = max(t[p * 2], t[p * 2 + 1]);
    }
  }
};
vector<int> g[300010];
int wg[300010], dad[300010], dep[300010];
void dfs1(int x) {
  wg[x] = 1;
  for (int y : g[x])
    if (y != dad[x]) {
      dad[y] = x;
      dep[y] = dep[x] + 1;
      dfs1(y);
      wg[x] += wg[y];
    }
}
int curpos, pos[300010], head[300010];
void hld(int x, int c) {
  if (c < 0) c = x;
  pos[x] = curpos++;
  head[x] = c;
  int mx = -1;
  for (int y : g[x])
    if (y != dad[x] && (mx < 0 || wg[mx] < wg[y])) mx = y;
  if (mx >= 0) hld(mx, c);
  for (int y : g[x])
    if (y != mx && y != dad[x]) hld(y, -1);
}
void hld_init() {
  dad[0] = -1;
  dep[0] = 0;
  dfs1(0);
  curpos = 0;
  hld(0, -1);
}
int query(int x, int y, RMQ& st) {
  int r = neutro;
  while (head[x] != head[y]) {
    if (dep[head[x]] > dep[head[y]]) swap(x, y);
    r = max(r, st.get(pos[head[y]], pos[y] + 1));
    y = dad[head[y]];
  }
  if (dep[x] > dep[y]) swap(x, y);
  r = max(r, st.get(pos[x], pos[y] + 1));
  return r;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n, q;
  cin >> n >> q;
  aho_init();
  vector<string> vs(n);
  vector<int> v(n, 0);
  nodeOfId = vector<int>(n);
  for (int i = (0); i < (n); i++) {
    cin >> vs[i];
    add_string(vs[i], i);
  }
  for (int i = (0); i < (((int)t.size())); i++) vals[i].insert(-1);
  for (int i = (1); i < (((int)t.size())); i++) g[get_link(i)].push_back(i);
  hld_init();
  RMQ st;
  st.init(((int)t.size()));
  for (int i = (0); i < (((int)t.size())); i++) st[pos[i]] = *vals[i].rbegin();
  st.updall();
  for (int _ = (0); _ < (q); _++) {
    int tq;
    cin >> tq;
    if (tq == 1) {
      int id, x;
      cin >> id >> x;
      id--;
      vals[nodeOfId[id]].erase(vals[nodeOfId[id]].find(v[id]));
      v[id] = x;
      vals[nodeOfId[id]].insert(v[id]);
      st.set(pos[nodeOfId[id]], *vals[nodeOfId[id]].rbegin());
    } else {
      string x;
      cin >> x;
      int node = 0, ans = -1;
      for (int i = (0); i < (((int)x.size())); i++) {
        node = go(node, x[i]);
        ans = max(ans, query(0, node, st));
      }
      cout << ans << '\n';
    }
  }
  return 0;
}
