Для простоты скажем, что «Тетрадь смерти» — это блокнот, который убивает того, чье имя в него вписывается.
С помощью него легко убивать, но довольно сложно поддерживать актуальную информацию о тех людях, кого вы еще не убили, но планируете. Поэтому вы решили создать «Систему управления базой данных смерти» — компьютерную программу, которая предоставляет удобный доступ к базе данных возможных жертв. Позвольте мне описать ее особенности.
Определим объект жертвы: у жертвы есть имя (необязательно уникальное), которое состоит только из строчных латинских букв, и целое значение подозрительности.
В начале программы пользователь вводит список из $$$n$$$ жертв в базу данных, значение подозрительности каждого устанавливается равным $$$0$$$.
Затем пользователь делает запросы двух типов:
Просто напоминаю, что программа не убивает людей, она только помогает искать их имена для записи в настоящую тетрадь. Поэтому список жертв в базе данных не меняется на протяжении всех запросов.
Ну и чего вы ждете? Напишите эту программу!
В первой строке записаны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$) — количество жертв и количество запросов, соответственно.
В каждой из следующих $$$n$$$ строк записано по одному слову $$$s_i$$$ — имя $$$i$$$-й жертвы. Каждое имя состоит только из строчных латинских букв.
В каждой из следующих $$$m$$$ строк записан запрос одного из двух типов:
Есть хотя бы один запрос второго типа. Суммарная длина строк $$$s_i$$$ не превосходит $$$3 \cdot 10^5$$$. Суммарная длина строк $$$q$$$ не превосходит $$$3 \cdot 10^5$$$.
На каждый запрос второго типа выведите одно целое число. Если нет такой жертвы, чье имя является подстрокой $$$q$$$, то выведите $$$-1$$$. Иначе выведите максимальное значение подозрительности жертвы, чье имя входит в $$$q$$$ как подстрока.
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 0 943 135832 943
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
0 4 4 -1 18 18 12 11
Название |
---|