#include <bits/stdc++.h>
using namespace std;
int n, m, i, val[300005];
struct node {
  multiset<int> val;
  int p, v;
  node *chd[26], *fail;
  node() {
    memset(chd, 0ll, sizeof(chd));
    fail = 0ll;
    p = v = 0;
    val.clear();
  }
};
node *root;
node *place[300005];
void resetAC() { root = new node(); }
char s[300005];
void insert() {
  node *now = root;
  int l = 0, len = strlen(s);
  while (l < len) {
    if (now->chd[s[l] - 'a'] == NULL) now->chd[s[l] - 'a'] = new node();
    now = now->chd[s[l] - 'a'];
    l++;
  }
  now->p++;
  place[i] = now;
  now->val.insert(0);
}
queue<node *> qAC;
void buildAC() {
  node *now, *q;
  int i;
  for (i = 0; i < 26; i++)
    if (root->chd[i] != NULL) root->chd[i]->fail = root, qAC.push(root->chd[i]);
  while (!qAC.empty()) {
    now = qAC.front();
    qAC.pop();
    for (i = 0; i < 26; i++)
      if (now->chd[i] != NULL) {
        q = now->fail;
        while (q != NULL && q->chd[i] == NULL) q = q->fail;
        if (q == NULL)
          now->chd[i]->fail = root;
        else
          now->chd[i]->fail = q->chd[i];
        qAC.push(now->chd[i]);
      }
  }
}
int AC() {
  node *now = root, *p;
  int ans = -1, len = strlen(s);
  for (int l = 0; l < len; l++) {
    while (now != root && now->chd[s[l] - 'a'] == NULL) now = now->fail;
    now = (now->chd[s[l] - 'a'] == NULL ? root : now->chd[s[l] - 'a']);
    p = now;
    while (p != NULL && p->v != i) {
      if (!p->val.empty()) {
        auto x = p->val.end();
        --x;
        ans = max(ans, *x);
      }
      p->v = i;
      p = p->fail;
    }
  }
  return ans;
}
char c;
int flag;
void read(int &x) {
  x = 0;
  c = getchar();
  flag = 1;
  while (c < '0' || c > '9') flag = (c == '-' ? -1 : flag), c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  x *= flag;
}
int opt;
int main() {
  resetAC();
  read(n);
  read(m);
  for (i = 1; i <= n; i++) {
    scanf("%s", s);
    insert();
  }
  buildAC();
  for (i = 1; i <= m; i++) {
    read(opt);
    if (opt == 1) {
      int x, vl;
      read(x);
      read(vl);
      place[x]->val.erase(place[x]->val.find(val[x]));
      val[x] = vl;
      place[x]->val.insert(val[x]);
    }
    if (opt == 2) {
      scanf("%s", s);
      cout << AC() << endl;
    }
  }
  return 0;
}
