Alphabet Permutations

Source: Codeforces

Version: Phuoc Hung OJ Extended

Problem Statement

Maintain a string over the first $k$ letters. Range assignments modify the string. For a permutation $p$, output the minimum number of repeated copies of $p$ needed so that the current string is a subsequence.

Input

The first line contains $n,m,k$, followed by string $s$. Then $m$ operations follow: 1 l r c assigns character $c$ on the range, while 2 p asks for $d(p)$ for a permutation $p$ of the first $k$ letters.

Output

For every type-2 operation, print $d(p)$.

Subtasks

• Subtask 1 (20%): size and operation count at most 30; all other validity conditions are unchanged.

• Subtask 2 (30%): size and operation count at most 3000; all other validity conditions are unchanged.

• Subtask 3 (50%): full constraints:

• $1\le n\le2\cdot10^5$

• $1\le m\le20000$

• $1\le k\le10$

Examples

Input

7 4 3
abacaba
1 3 5 b
2 abc
1 4 4 c
2 cba

Output

6
5

Explanation

After the first assignment the string is abbbbba; permutation abc needs 6 copies. After the next assignment the string is abbcbba; permutation cba needs 5 copies.