Для простоты скажем, что «Тетрадь смерти» — это блокнот, который убивает того, чье имя в него вписывается.
С помощью него легко убивать, но довольно сложно поддерживать актуальную информацию о тех людях, кого вы еще не убили, но планируете. Поэтому вы решили создать «Систему управления базой данных смерти» — компьютерную программу, которая предоставляет удобный доступ к базе данных возможных жертв. Позвольте мне описать ее особенности.
Определим объект жертвы: у жертвы есть имя (необязательно уникальное), которое состоит только из строчных латинских букв, и целое значение подозрительности.
В начале программы пользователь вводит список из \(n\) жертв в базу данных, значение подозрительности каждого устанавливается равным \(0\).
Затем пользователь делает запросы двух типов:
- \(1~i~x\) — выставить значение подозрительности \(i\)-й жертвы равным \(x\);
- \(2~q\) — по заданной строке \(q\) найти максимальное значение подозрительности жертвы, чье имя входит в \(q\) как подстрока (символы на подряд идущих позициях).
Просто напоминаю, что программа не убивает людей, она только помогает искать их имена для записи в настоящую тетрадь. Поэтому список жертв в базе данных не меняется на протяжении всех запросов.
Ну и чего вы ждете? Напишите эту программу!
Выходные данные
На каждый запрос второго типа выведите одно целое число. Если нет такой жертвы, чье имя является подстрокой \(q\), то выведите \(-1\). Иначе выведите максимальное значение подозрительности жертвы, чье имя входит в \(q\) как подстрока.