#include <bits/stdc++.h>
using namespace std;
int trie[303030][26], belong[303030], fail[303030], tot = 0, rt = 0,
                                                    orw[303030];
multiset<int> w[303030];
int n, m;
char s[303030];
int clrsta[303030], top = 0;
int vis[303030];
inline void build() {
  queue<int> q;
  for (int i = 0; i < 26; ++i) {
    if (trie[rt][i]) {
      fail[trie[rt][i]] = rt;
      q.push(trie[rt][i]);
    }
  }
  while (q.size()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; ++i) {
      if (trie[u][i]) {
        fail[trie[u][i]] = trie[fail[u]][i];
        q.push(trie[u][i]);
      } else {
        trie[u][i] = trie[fail[u]][i];
      }
    }
  }
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1, len, cur; i <= n; ++i) {
    scanf("%s", s + 1);
    len = strlen(s + 1);
    cur = rt;
    for (int j = 1; j <= len; ++j) {
      if (!trie[cur][s[j] - 'a']) trie[cur][s[j] - 'a'] = ++tot;
      cur = trie[cur][s[j] - 'a'];
    }
    belong[i] = cur;
    w[cur].insert(0);
  }
  build();
  for (int i = 1, op; i <= m; ++i) {
    scanf("%d", &op);
    if (op == 1) {
      int i, x;
      scanf("%d%d", &i, &x);
      w[belong[i]].erase(w[belong[i]].find(-orw[i]));
      w[belong[i]].insert(-x);
      orw[i] = x;
    } else {
      scanf("%s", s + 1);
      int len = strlen(s + 1);
      int cur = rt, cpcur;
      int ans = -1;
      for (int j = 1; j <= len; ++j) {
        cpcur = cur = trie[cur][s[j] - 'a'];
        while (!vis[cpcur]) {
          if (w[cpcur].size()) ans = max(ans, -*(w[cpcur].begin()));
          vis[cpcur] = 1;
          clrsta[++top] = cpcur;
          cpcur = fail[cpcur];
        }
      }
      printf("%d\n", ans);
      while (top) vis[clrsta[top--]] = 0;
    }
  }
}
