为了简单起见,我们假设“死亡笔记”是一本笔记本,当一个人的名字写在里面时就会杀死一个人。
用它杀死人很容易,但要追踪你还没有杀死但仍计划杀死的人却相当困难。您决定制作一个“死亡数据库管理系统”——一种计算机程序,可以轻松访问可能受害者的数据库。让我向您描述一下它的规格。
让我们定义一个受害者实体:受害者有一个仅由小写拉丁字母和整数可疑值组成的名称(不一定是唯一的)。
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