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

const int maxN = 3e5 + 10;

struct Node
{
	int trans[26], fail;
}st[maxN + 1];

int n, m, cnt;
int id[maxN + 1], lst[maxN + 1], val[maxN + 1];
char str[maxN + 1];

vector<int> son[maxN + 1];

multiset<int> s[maxN + 1];

inline int insert()
{
	int cur = 0, len = strlen(str + 1);
	for(int i = 1; i <= len; i++)
	{
		int c = str[i] - 'a';
		if(!st[cur].trans[c]) st[cur].trans[c] = ++ cnt;
		cur = st[cur].trans[c];
	}
	return cur;
}

inline void get_fail()
{
	queue<int> q;
	for(int c = 0; c < 26; c++)
		if(st[0].trans[c]) q.push(st[0].trans[c]);
	while(!q.empty())
	{
		int cur = q.front(); q.pop();
		for(int c = 0; c < 26; c++)
			if(st[cur].trans[c]) st[ st[cur].trans[c] ].fail = st[ st[cur].fail ].trans[c], q.push(st[cur].trans[c]);
			else st[cur].trans[c] = st[ st[cur].fail ].trans[c];
	}
}

inline void dfs(int u)
{
	for(int i = 0; i < son[u].size(); i++)
	{
		int v = son[u][i];
		if(!s[u].size()) lst[v] = lst[u];
		else lst[v] = u;
		dfs(v);
	}
}

int main()
{
	scanf("%d %d", &n, &m);
	for(int i = 1; i <= n; i++)
	{
		scanf("%s", str + 1);
		id[i] = insert();
		s[ id[i] ].insert(val[i] = 0);
	}

	get_fail();

	for(int i = 1; i <= cnt; i++) son[ st[i].fail ].push_back(i);

	dfs(0);

	while(m --)
	{
		int op;
		scanf("%d", &op);
		if(op == 1)
		{
			int x, y;
			scanf("%d %d", &x, &y);
			s[ id[x] ].erase(s[ id[x] ].find(val[x]));
			val[x] = y;
			s[ id[x] ].insert(val[x]);
		}
		else
		{
			scanf("%s", str + 1);
			int cur = 0, len = strlen(str + 1), ans = -1;
			for(int i = 1; i <= len; i++)
			{
				int c = str[i] - 'a';
				cur = st[cur].trans[c];
				for(int t = cur; t; t = lst[t])
					if(s[t].size()) ans = max(ans, (*s[t].rbegin()));
			}
			printf("%d\n", ans);
		}
	}
	return 0;
}