CF610E.Alphabet Permutations

You are given a string s of length n, consisting of first k lowercase English letters.

We define a c-repeat of some string q as a string, consisting of c copies of the string q. For example, string "acbacbacbacb" is a 4-repeat of the string "acb".

Let's say that string a contains string b as a subsequence, if string b can be obtained from a by erasing some symbols.

Let p be a string that represents some permutation of the first k lowercase English letters. We define function d(p) as the smallest integer such that a d(p)-repeat of the string p contains string s as a subsequence.

There are m operations of one of two types that can be applied to string s:

1. Replace all characters at positions from l__i to r__i by a character c__i.
2. For the given p, that is a permutation of first k lowercase English letters, find the value of function d(p).

All operations are performed sequentially, in the order they appear in the input. Your task is to determine the values of function d(p) for all operations of the second type.

给你一个长度为 $n$ 的字符串 $s$，它仅由前 $k$ 个小写英文字母组成。

我们定义字符串 $q$ 的一个 $c$-重复（$c$-repeat）为由 $c$ 个 $q$ 的副本拼接而成的字符串。例如，字符串 "acbacbacbacb" 是字符串 "acb" 的 4-重复。

若字符串 $b$ 可通过从字符串 $a$ 中删除若干字符（不改变剩余字符的相对顺序）而得到，则称字符串 $a$ 包含字符串 $b$ 作为其子序列（subsequence）。

设 $p$ 是前 $k$ 个小写英文字母的一个排列。我们定义函数 $d(p)$ 为满足“$p$ 的 $d(p)$-重复包含 $s$ 作为子序列”的最小整数。

对字符串 $s$ 共进行 $m$ 次操作，每次操作属于以下两种类型之一：

1. 将位置区间 $[l_i, r_i]$ 内的所有字符替换为字符 $c_i$；
2. 给定一个前 $k$ 个小写英文字母的排列 $p$，求函数 $d(p)$ 的值。

所有操作按输入中出现的顺序依次执行。你的任务是：对每一个第 2 类操作，输出对应的 $d(p)$ 值。

The first line contains three positive integers n, m and k (1 ≤ n ≤ 200 000, 1 ≤ m ≤ 20000, 1 ≤ k ≤ 10) — the length of the string s, the number of operations and the size of the alphabet respectively. The second line contains the string s itself.

Each of the following lines m contains a description of some operation:

1. Operation of the first type starts with 1 followed by a triple l__i, r__i and c__i, that denotes replacement of all characters at positions from l__i to r__i by character c__i (1 ≤ l__i ≤ r__i ≤ n, c__i is one of the first k lowercase English letters).
2. Operation of the second type starts with 2 followed by a permutation of the first k lowercase English letters.

第一行包含三个正整数 $n$、$m$ 和 $k$（$1 ≤ n ≤ 200\,000$，$1 ≤ m ≤ 20\,000$，$1 ≤ k ≤ 10$），分别表示字符串 $s$ 的长度、操作次数以及字母表的大小。第二行包含字符串 $s$ 本身。

接下来的 $m$ 行中，每行描述一个操作：

1. 第一类操作以 1 开头，后跟一个三元组 $l_i$、$r_i$ 和 $c_i$，表示将位置从 $l_i$ 到 $r_i$（含端点）的所有字符替换为字符 $c_i$（$1 ≤ l_i ≤ r_i ≤ n$，$c_i$ 是前 $k$ 个小写英文字母之一）。
2. 第二类操作以 2 开头，后跟前 $k$ 个小写英文字母的一个排列。

For each query of the second type the value of function d(p).

对于每个第二类查询，函数 $d(p)$ 的值。

After the first operation the string s will be abbbbba.

In the second operation the answer is 6-repeat of abc: ABcaBcaBcaBcaBcAbc.

After the third operation the string s will be abbcbba.

In the fourth operation the answer is 5-repeat of cba: cbAcBacBaCBacBA.

Uppercase letters means the occurrences of symbols from the string s.

第一次操作后，字符串 $s$ 将变为 abbbbba。

第二次操作的答案是 abc 的 6 次重复：ABcaBcaBcaBcaBcAbc。

第三次操作后，字符串 $s$ 将变为 abbcbba。

第四次操作的答案是 cba 的 5 次重复：cbAcBacBaCBacBA。

大写字母表示字符串 $s$ 中对应字符的出现位置。