给定一个长度为 n 的字符串 s,由前 k 个小写英文字母组成。
我们将某个字符串 q 的 c 次重复定义为字符串,由字符串 q 的 c 个副本组成。例如,字符串“acbacbacbacb”是字符串“acb”的 4 次重复。
假设字符串 a 包含字符串 b 作为子序列,如果字符串 b 可以通过删除一些符号从 a 中获得。
令 p 为表示前 k 个小写英文字母的某种排列的字符串。我们将函数 d(p) 定义为最小整数,使得字符串 p 的 d(p) 重复包含字符串 s 作为子序列。
有 m 个可应用于字符串 s 的两种类型之一的操作:
1. 将 li 到 ri 位置上的所有字符替换为字符 ci。
2. 对于给定的 p,即前 k 个小写英文字母的排列,求函数 d(p) 的值。
所有操作均按照它们在输入中出现的顺序顺序执行。您的任务是确定第二类所有操作的函数 d(p) 值。
输入
第一行包含三个正整数 n、m 和 k (1 ≤ n ≤ 200 000, 1 ≤ m ≤ 20000, 1 ≤ k ≤ 10)——分别是字符串 s 的长度、运算次数和字母表的大小。第二行包含字符串 s 本身。
以下每一行 m 包含某些操作的描述:
1、第一类操作以 1 开头,后接三元组 li、ri、ci,表示将 li 到 ri 位置上的所有字符替换为字符 ci(1 ≤ li ≤ ri ≤ n,ci 为前 k 个小写英文字母之一)。
2、第二种操作以2开头,后面是前k个小写英文字母的排列。
输出
对于第二类型的每个查询,函数 d(p) 的值。
示例
输入 #1
7 4 3 abacaba 1 3 5 b 2 abc 1 4 4 c 2 cba
输出 #1
6 5
注意
第一次操作后,字符串 s 将是 abbbbba。
在第二个操作中,答案是 abc 的 6 次重复:ABcaBcaBcaBcaBcAbc。
第三次操作后,字符串 s 将是 abbcbba。
在第四次操作中,答案是 cba 的 5 次重复:cbAcBacBaCBacBA。
大写字母表示字符串 s 中出现的符号。