E. Перестановки алфавита
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дана строка s длины n, состоящая из первых k строчных букв английского алфавита.

Будем называть c-повтором некоторой строки q строку, состоящую из c копий строки q. Например, строка "acbacbacbacb" является 4-повтором строки "acb".

Будем также говорить, что строка a содержит строку b как подпоследовательность, если строку b можно получить из a выкидыванием некоторых символов.

Пусть p — строка, представляющая собой некоторую перестановку первых k строчных букв английского алфавита. Введём функцию d(p), равную наименьшему целому числу, такому что строка s является подпоследовательностью d(p)-повтора строки p.

К строке s применяют m операций одного из двух типов:

  1. Заменить все символы на позициях с li-й по ri-ю на символ ci.
  2. Для заданной p, являющейся перестановкой первых k букв английского алфавита, найти значение функции d(p).

Все операции выполняются последовательно, в порядке следования во входных данных. Ваша задача вывести значения функции d(p) для всех операций второго типа.

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

В первой строке находятся три целых положительных числа n, m, k (1 ≤ n ≤ 200 000, 1 ≤ m ≤ 20 000, 1 ≤ k ≤ 10) — длина строки s, количество операций и размер алфавита соответственно.

Вторая строка содержит строку s.

В каждой из следующих m строк находится описание очередной операции:

  1. Операция первого типа задаётся числом 1 и тройкой li, ri и ci, обозначающей замену символов в позициях с li-й по ri-ю на символ ci (1 ≤ li ≤ ri ≤ n, ci является одной из первых k строчных букв английского алфавита).
  2. Операция второго типа задаётся числом 2 и перестановкой pi первых k строчных букв английского алфавита.
Выходные данные

Для каждого запроса второго типа выведите в отдельной строке значение функции d(pi).

Примеры
Входные данные
7 4 3
abacaba
1 3 5 b
2 abc
1 4 4 c
2 cba
Выходные данные
6
5
Примечание

После первой операции строка станет равной abbbbba.

Во второй операции в качестве ответа нужно взять 6-повтор строки abc: ABcaBcaBcaBcaBcAbc.

После третьего запроса строка станет равной abbcbba.

В четвертой операции в качестве ответа нужно взять 5-повтор строки cba: cbAcBacBaCBacBA.

Заглавными буквами обозначены вхождения символов из строки s.