← 返回题目列表

Codeforces · 610/E

E. 字母排列

中文机器翻译题面 查看原题

给定一个长度为 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 中出现的符号。