← 返回题目列表

Codeforces · 1437/G

G. 死亡 DBMS

中文机器翻译题面 查看原题

为了简单起见,我们假设“死亡笔记”是一本笔记本,当一个人的名字写在里面时就会杀死一个人。

用它杀死人很容易,但要追踪你还没有杀死但仍计划杀死的人却相当困难。您决定制作一个“死亡数据库管理系统”——一种计算机程序,可以轻松访问可能受害者的数据库。让我向您描述一下它的规格。

让我们定义一个受害者实体:受害者有一个仅由小写拉丁字母和整数可疑值组成的名称(不一定是唯一的)。

At the start of the program the user enters a list of $$$n$$$ victim names into a database, each suspicion value is set to $$$0$$$.

然后用户进行两种类型的查询:

- $$$1~i~x$$$ — 将第$$$i$$$个受害者的怀疑值设置为$$$x$$$;
- $$$2~q$$$ - 给定一个字符串 $$$q$$$ 找到名称为 $$$q$$$ 的连续子字符串的受害者的最大怀疑值。

只是提醒你,这个程序不会杀人,它只是帮助搜索名字并写在实际的笔记本上。因此,数据库中的受害者列表在整个查询过程中不会发生变化。

你还在等什么?现在就写这个程序吧!

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$)——分别是受害者数量和查询数量。

Each of the next $$$n$$$ lines contains a single string $$$s_i$$$ — the name of the $$$i$$$-th victim.每个名称仅由小写拉丁字母组成。

接下来的 $$$m$$$ 行包含以下两种类型之一的查询:

- $$$1~i~x$$$ ($$$1 \le i \le n$$$, $$$0 \le x \le 10^9$$$) — 将第 $$$i$$$ 个受害者的怀疑值更改为 $$$x$$$;
- $$$2~q$$$ - 给定一个仅由小写拉丁字母组成的字符串 $$$q$$$,找到名称为 $$$q$$$ 的连续子字符串的受害者的最大怀疑值。

There is at least one query of the second type. The total length of the strings $$$s_i$$$ doesn't exceed $$$3 \cdot 10^5$$$.字符串 $$$q$$$ 的总长度不超过 $$$3 \cdot 10^5$$$。

输出

For each query of the second type print an integer value.如果没有受害者姓名是 $$$q$$$ 的连续子字符串,则打印 $$$-1$$$。 Otherwise, print the maximum suspicion value of a victim whose name is a contiguous substring of $$$q$$$.

示例

输入 #1

5 8
kurou
takuo
takeshi
naomi
shingo
2 nakiraomi
2 abanaomicaba
1 3 943
2 takuotakeshishingo
1 5 135832
2 shingotakeshi
1 5 0
2 shingotakeshi

输出 #1

-1
0
943
135832
943

输入 #2

6 15
a
ab
ba
b
a
ba
2 aa
1 4 4
2 bbb
1 2 1
1 2 18
2 b
2 c
1 6 10
2 aba
2 abbbba
1 2 12
2 bbaaab
1 1 11
1 5 5
2 baa

输出 #2

0
4
4
-1
18
18
12
11