#include <bits/stdc++.h>
using namespace std;
const int maxn = 300010;
multiset<int> val[maxn];
struct Trie {
  int next[maxn][26], fail[maxn], end[maxn];
  int last[maxn];
  int root, L;
  int newnode() {
    for (int i = 0; i < 26; i++) next[L][i] = -1;
    fail[L] = last[L] = end[L] = 0;
    return L++;
  }
  void init() {
    L = 0;
    root = newnode();
  }
  int insert(char buf[], int v) {
    int len = strlen(buf);
    int now = root;
    for (int i = 0; i < len; i++) {
      if (next[now][buf[i] - 'a'] == -1) next[now][buf[i] - 'a'] = newnode();
      now = next[now][buf[i] - 'a'];
    }
    end[now]++;
    val[now].insert(v);
    return now;
  }
  void build() {
    queue<int> Q;
    fail[root] = root;
    for (int i = 0; i < 26; i++) {
      if (next[root][i] == -1)
        next[root][i] = root;
      else {
        fail[next[root][i]] = root;
        Q.push(next[root][i]);
      }
    }
    while (!Q.empty()) {
      int now = Q.front();
      Q.pop();
      for (int i = 0; i < 26; i++) {
        if (next[now][i] == -1)
          next[now][i] = next[fail[now]][i];
        else {
          int son = next[now][i];
          fail[son] = next[fail[now]][i];
          last[son] = end[fail[son]] ? fail[son] : last[fail[son]];
          Q.push(next[now][i]);
        }
      }
    }
  }
  int count(int x) {
    int res = -1;
    for (int j = x; j && end[j] != -1; j = last[j]) {
      if (end[j]) res = max(res, *val[j].rbegin());
    }
    return res;
  }
  void query(char buf[]) {
    int len = strlen(buf);
    int now = root;
    int res = -1;
    for (int i = 0; i < len; i++) {
      now = next[now][buf[i] - 'a'];
      if (end[now] != -1)
        res = max(res, count(now));
      else if (end[last[now]] != -1)
        res = max(res, count(last[now]));
    }
    printf("%d\n", res);
  }
  void ch(int pos, int x, int y) {
    auto it = val[pos].lower_bound(x);
    val[pos].erase(it);
    val[pos].insert(y);
  }
} ac;
char s[maxn];
int pos[maxn], w[maxn];
int main() {
  int n, m;
  ac.init();
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%s", s);
    pos[i] = ac.insert(s, 0);
    w[i] = 0;
  }
  ac.build();
  int op, x, y;
  while (m--) {
    scanf("%d", &op);
    if (op == 1) {
      scanf("%d%d", &x, &y);
      ac.ch(pos[x], w[x], y);
      w[x] = y;
    } else {
      scanf("%s", s);
      ac.query(s);
    }
  }
  return 0;
}
