#include <bits/stdc++.h>
using namespace std;
int trie[300005][26];
int position[300005];
vector<int> adj[300005];
vector<pair<int, int> > upd[300005];
vector<int> qq[300005], tt[300005];
void add(char *s, int k, int id) {
  static int pos = 1;
  int node = 0;
  for (int i = 0; i < k; ++i) {
    int ind = s[i] - 'a';
    if (!trie[node][ind]) {
      trie[node][ind] = pos++;
    }
    node = trie[node][ind];
  }
  tt[node].push_back(id);
}
int q[300005], fail[300005];
void computeFail() {
  int l = 1, r = 0;
  for (int i = 0; i < 26; ++i) {
    if (trie[0][i]) {
      q[++r] = trie[0][i];
    }
  }
  for (; l <= r; ++l) {
    int node = q[l];
    for (int i = 0; i < 26; ++i) {
      if (trie[node][i]) {
        int nnode = trie[node][i];
        q[++r] = nnode;
        fail[nnode] = trie[fail[node]][i];
      } else {
        trie[node][i] = trie[fail[node]][i];
      }
    }
    adj[fail[node]].push_back(node);
  }
}
void go(char *s, int len, int id) {
  int cur = 0;
  for (int i = 0; i < len; ++i) {
    cur = trie[cur][s[i] - 'a'];
    qq[cur].push_back(id);
  }
}
char s[300005];
int ret[300005];
int type[300005], lt[300005];
int m;
stack<int *> pointer;
stack<int> value;
int seg[300005 * 4];
void init(int pos, int l, int r) {
  seg[pos] = -1;
  if (l == r) {
    return;
  }
  int mid = (l + r) / 2;
  init(pos * 2, l, mid);
  init(pos * 2 + 1, mid + 1, r);
  seg[pos] = seg[pos * 2] + seg[pos * 2 + 1];
}
int query(int pos, int l, int r, int ind) {
  if (l == r) {
    return seg[pos];
  }
  int ret = -1;
  int mid = (l + r) / 2;
  if (ind <= mid) {
    ret = query(pos * 2, l, mid, ind);
  } else {
    ret = query(pos * 2 + 1, mid + 1, r, ind);
  }
  return max(seg[pos], ret);
}
void update(int pos, int l, int r, int ql, int qr, int x) {
  if (r < ql || qr < l) {
    return;
  }
  if (ql <= l && r <= qr) {
    pointer.push(&seg[pos]);
    value.push(seg[pos]);
    seg[pos] = max(seg[pos], x);
    return;
  }
  int mid = (l + r) / 2;
  update(pos * 2, l, mid, ql, qr, x);
  update(pos * 2 + 1, mid + 1, r, ql, qr, x);
}
void rollback() {
  int *p = pointer.top();
  *p = value.top();
  pointer.pop();
  value.pop();
}
void dfs(int node, int par) {
  int sz = pointer.size();
  for (int id : tt[node]) {
    int rp = m;
    for (pair<int, int> t : upd[id]) {
      if (t.second <= rp) {
        update(1, 0, m, t.second, rp, t.first);
        rp = t.second - 1;
      }
    }
  }
  for (int x : qq[node]) {
    ret[x] = max(ret[x], query(1, 0, m, x));
  }
  for (int ch : adj[node]) {
    assert(ch != par);
    dfs(ch, node);
  }
  while (sz < (int)pointer.size()) {
    rollback();
  }
}
void solve() {
  int n;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    scanf(" %s ", s);
    add(s, strlen(s), i);
  }
  computeFail();
  for (int i = 1; i <= n; ++i) {
    upd[i].push_back({0, 0});
  }
  for (int i = 1; i <= m; ++i) {
    ret[i] = -1;
    scanf("%d ", &type[i]);
    if (type[i] == 1) {
      int id, x;
      scanf("%d %d ", &id, &x);
      upd[id].push_back({x, i});
    } else {
      scanf(" %s ", s);
      go(s, strlen(s), i);
    }
  }
  for (int i = 1; i <= n; ++i) {
    reverse(upd[i].begin(), upd[i].end());
  }
  init(1, 0, m);
  dfs(0, 0);
  for (int i = 1; i <= m; ++i) {
    if (type[i] == 2) {
      printf("%d\n", ret[i]);
    }
  }
}
int main() {
  solve();
  return 0;
}
