#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
int trie[N][26], cnt;
int strtag[N], fail[N];
bool cntword[N];
multiset<int> val[N];
int a[N];
void insert(char* str, int n, int tag)
{
	int root = 0;
	for (int i = 1; i <= n; ++i)
	{
		int nxt = str[i] - 'a';
		if (!trie[root][nxt])
			trie[root][nxt] = ++cnt;
		root = trie[root][nxt];
	}
	val[root].insert(0);
	strtag[tag] = root;
}
void getfail()
{
	queue<int>q;
	for (int i = 0; i < 26; ++i)
		if (trie[0][i])
			fail[trie[0][i]] = 0, q.push(trie[0][i]);
	while (q.size())
	{
		int now = q.front();
		q.pop();
		for (int i = 0; i < 26; ++i)
		{
			if (trie[now][i])
				fail[trie[now][i]] = trie[fail[now]][i], q.push(trie[now][i]);
			else
				trie[now][i] = trie[fail[now]][i];
		}
	}
}
int buf[N];
int query(char* str, int n)
{
	int top = 0;
	int root = 0, ans = -1;
	for (int i = 1; i <= n; ++i)
	{
		int nxt = str[i] - 'a';
		root = trie[root][nxt];
		for (int j = root; j && !cntword[j]; j = fail[j])
		{
			if (val[j].size())
				ans = max(ans, *val[j].rbegin());
			cntword[j] = 1;
			buf[++top] = j;
		}
	}
	for (int i = 1; i <= top; ++i)
		cntword[buf[i]] = 0;
	return ans;
}
char s[N];
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i)
		scanf("%s", s + 1), insert(s, strlen(s + 1), i);
	getfail();
	while (m--)
	{
		int op;
		scanf("%d\n", &op);
		if (op == 1)
		{
			int pos, nv;
			scanf("%d%d", &pos, &nv);
			auto& it = val[strtag[pos]];
			it.erase(it.lower_bound(a[pos]));
			a[pos] = nv;
			it.insert(nv);
		}
		else
		{
			scanf("%s", s + 1);
			printf("%d\n", query(s, strlen(s + 1)));
		}
	}
	return 0;
}