#include <bits/stdc++.h>
using namespace std;

constexpr int MAXN = 3e5 + 5, CHARSET = 26;

int total, fail[MAXN], to[MAXN][CHARSET];
int val[MAXN], endPos[MAXN], curVal[MAXN], nextPos[MAXN];
multiset<int> heap[MAXN];

int main(int argc, char *argv[]) {
  cin.sync_with_stdio(false), cin.tie(nullptr);

  memset(val, -1, sizeof val);

  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    string s;
    cin >> s;
    int cur = 0;
    for (auto c : s) {
      if (!to[cur][c - 'a']) {
        to[cur][c - 'a'] = ++total;
      }
      cur = to[cur][c - 'a'];
    }
    endPos[i] = cur;
    heap[endPos[i]].insert(0);
    val[endPos[i]] = 0;
  }
  queue<int> que;
  for (int i = 0; i < CHARSET; i++) {
    if (to[0][i]) {
      que.push(to[0][i]);
    }
  }
  while (!que.empty()) {
    int u = que.front();
    que.pop();

    nextPos[u] = (val[fail[u]] != -1) ? fail[u] : nextPos[fail[u]];
    for (int i = 0; i < CHARSET; i++) {
      if (to[u][i]) {
        fail[to[u][i]] = to[fail[u]][i];
        que.push(to[u][i]);
      } else {
        to[u][i] = to[fail[u]][i];
      }
    }
  }
  while (m--) {
    int op;
    cin >> op;
    if (op == 1) {
      int i, x;
      cin >> i >> x;
      heap[endPos[i]].erase(heap[endPos[i]].find(curVal[i]));
      curVal[i] = x;
      heap[endPos[i]].insert(x);
      val[endPos[i]] = *heap[endPos[i]].rbegin();
    } else if (op == 2) {
      string s;
      cin >> s;
      int cur = 0, res = -1;
      for (auto c : s) {
        cur = to[cur][c - 'a'];
        for (int ptr = cur; ptr; ptr = nextPos[ptr]) {
          res = max(res, val[ptr]);
        }
      }
      cout << res << "\n";
    }
  }
}