G. СУБД смерти
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для простоты скажем, что «Тетрадь смерти» — это блокнот, который убивает того, чье имя в него вписывается.

С помощью него легко убивать, но довольно сложно поддерживать актуальную информацию о тех людях, кого вы еще не убили, но планируете. Поэтому вы решили создать «Систему управления базой данных смерти» — компьютерную программу, которая предоставляет удобный доступ к базе данных возможных жертв. Позвольте мне описать ее особенности.

Определим объект жертвы: у жертвы есть имя (необязательно уникальное), которое состоит только из строчных латинских букв, и целое значение подозрительности.

В начале программы пользователь вводит список из $$$n$$$ жертв в базу данных, значение подозрительности каждого устанавливается равным $$$0$$$.

Затем пользователь делает запросы двух типов:

  • $$$1~i~x$$$ — выставить значение подозрительности $$$i$$$-й жертвы равным $$$x$$$;
  • $$$2~q$$$ — по заданной строке $$$q$$$ найти максимальное значение подозрительности жертвы, чье имя входит в $$$q$$$ как подстрока (символы на подряд идущих позициях).

Просто напоминаю, что программа не убивает людей, она только помогает искать их имена для записи в настоящую тетрадь. Поэтому список жертв в базе данных не меняется на протяжении всех запросов.

Ну и чего вы ждете? Напишите эту программу!

Входные данные

В первой строке записаны два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 3 \cdot 10^5$$$) — количество жертв и количество запросов, соответственно.

В каждой из следующих $$$n$$$ строк записано по одному слову $$$s_i$$$ — имя $$$i$$$-й жертвы. Каждое имя состоит только из строчных латинских букв.

В каждой из следующих $$$m$$$ строк записан запрос одного из двух типов:

  • $$$1~i~x$$$ ($$$1 \le i \le n$$$, $$$0 \le x \le 10^9$$$) — выставить значение подозрительности $$$i$$$-й жертвы равным $$$x$$$;
  • $$$2~q$$$ — по заданной строке $$$q$$$, состоящей только из строчных латинских букв, найти максимальное значение подозрительности жертвы, чье имя входит в $$$q$$$ как подстрока (символы на подряд идущих позициях).

Есть хотя бы один запрос второго типа. Суммарная длина строк $$$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