#include <bits/stdc++.h>
using namespace std;
const int M = 1000000007;
const int MM = 998244353;
const long double PI = acos(-1);
template <typename T, typename U>
static inline void amin(T &x, U y) {
  if (y < x) x = y;
}
template <typename T, typename U>
static inline void amax(T &x, U y) {
  if (x < y) x = y;
}
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  return os << '(' << p.first << "," << p.second << ')';
}
const int LEN = 400005;
vector<int> g[LEN];
struct aho_corasick {
  struct Vertex {
    map<char, int> next;
    int cnt, link;
    Vertex() : cnt(0) {}
  };
  Vertex tr[LEN];
  int sz = 0;
  aho_corasick() { sz = 1; }
  int add_word(string &s) {
    int v = 0;
    for (auto j : s) {
      if (!tr[v].next.count(j)) tr[v].next[j] = sz++;
      v = tr[v].next[j];
    }
    ++tr[v].cnt;
    return v;
  }
  void gen_links() {
    queue<int> Q;
    tr[0].link = -1;
    Q.push(0);
    while (!Q.empty()) {
      int u = Q.front();
      Q.pop();
      for (auto j : tr[u].next) {
        char c = j.first;
        int v = j.second;
        int k = tr[u].link;
        while (k != -1 && !tr[k].next.count(c)) k = tr[k].link;
        if (k == -1)
          k = 0;
        else
          k = tr[k].next[c];
        tr[v].link = k;
        Q.push(v);
      }
    }
    gen_tree();
  }
  void gen_tree() {
    for (int i = 1; i < sz; ++i) {
      g[tr[i].link].push_back(i);
    }
  }
  void print_dfs(int u = 0) {
    for (auto j : tr[u].next) {
      cout << j.first << " ";
      print_dfs(j.second);
    }
  }
} aho;
const int N = LEN;
int in[N], out[N], cur = 1, head[N], sub[N], par[N];
struct node {
  int mx = -1;
} fake;
struct SEGTREE {
  int a[N];
  SEGTREE() {}
  node tree[4 * N];
  int lazy[4 * N];
  inline node combine(node a, node b) {
    node ret;
    ret.mx = max(a.mx, b.mx);
    return ret;
  }
  inline node make_node(int val) {
    node ret;
    ret.mx = val;
    return ret;
  }
  void buildTree(int v, int st, int en) {
    if (st == en) {
      tree[v] = make_node(a[st]);
      return;
    }
    int mid = (st + en) >> 1;
    buildTree(v << 1, st, mid);
    buildTree(v << 1 | 1, mid + 1, en);
    tree[v] = combine(tree[v << 1], tree[v << 1 | 1]);
  }
  void update(int v, int st, int en, int in, int val) {
    int mid = (st + en) >> 1;
    if (st == en) {
      tree[v] = make_node(val);
      a[st] = val;
      return;
    }
    if (in <= mid)
      update(v << 1, st, mid, in, val);
    else
      update(v << 1 | 1, mid + 1, en, in, val);
    tree[v] = combine(tree[v << 1], tree[v << 1 | 1]);
  }
  node query(int v, int st, int en, int l, int r) {
    if (en < l || st > r) return fake;
    if (st >= l && en <= r) return tree[v];
    int mid = (st + en) >> 1;
    return combine(query(v << 1, st, mid, l, r),
                   query(v << 1 | 1, mid + 1, en, l, r));
  }
} seg;
void dfs_sz(int u = 0, int p = 0) {
  par[u] = p;
  sub[u] = 1;
  for (auto j : g[u]) dfs_sz(j, u), sub[u] += sub[j];
}
void dfs(int u = 0, int h = 0) {
  head[u] = h;
  in[u] = cur++;
  int mx = -1, bc = -1;
  for (auto j : g[u])
    if (sub[j] > mx) mx = sub[j], bc = j;
  if (bc != -1) dfs(bc, h);
  for (auto j : g[u])
    if (j != bc) dfs(j, j);
  out[u] = cur - 1;
}
multiset<int> endpts[N];
int _runtimeTerror_() {
  int n, m;
  cin >> n >> m;
  vector<int> end(n + 1, -1), val(n + 1, 0);
  string s;
  for (int i = 1; i < N; ++i) seg.a[i] = -1;
  for (int i = 1; i <= n; ++i) {
    cin >> s;
    end[i] = aho.add_word(s);
    endpts[end[i]].insert(0);
  }
  aho.gen_links();
  dfs_sz();
  dfs(0, 0);
  for (int i = 1; i <= n; ++i) seg.a[in[end[i]]] = 0;
  seg.buildTree(1, 1, aho.sz);
  assert(cur == aho.sz + 1);
  auto query = [&](int v) {
    int ans = -1;
    while (v) {
      assert(in[head[v]] <= in[v]);
      amax(ans, seg.query(1, 1, aho.sz, in[head[v]], in[v]).mx);
      v = par[head[v]];
    }
    return ans;
  };
  for (int i = 1; i <= m; ++i) {
    int tt;
    cin >> tt;
    if (tt == 1) {
      int i, x;
      cin >> i >> x;
      endpts[end[i]].erase(endpts[end[i]].find(val[i]));
      endpts[end[i]].insert(x);
      seg.update(1, 1, aho.sz, in[end[i]], *endpts[end[i]].rbegin());
      val[i] = x;
    } else {
      int cur = 0;
      string q;
      cin >> q;
      int ans = -1;
      for (int j = 0; j < (int)q.size();) {
        if (aho.tr[cur].next.count(q[j])) {
          cur = aho.tr[cur].next[q[j]];
          amax(ans, query(cur));
          ++j;
        } else {
          cur = aho.tr[cur].link;
        }
        if (cur == -1) cur = 0, ++j;
      }
      cout << ans << "\n";
    }
  }
  return 0;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int TESTS = 1;
  while (TESTS--) _runtimeTerror_();
  return 0;
}
