Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Alphabet Permutations

time limit per test

1 secondmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou 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*:

- Replace all characters at positions from
*l*_{i}to*r*_{i}by a character*c*_{i}. - 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.

Input

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:

- 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). - Operation of the second type starts with 2 followed by a permutation of the first
*k*lowercase English letters.

Output

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

Examples

Input

7 4 3

abacaba

1 3 5 b

2 abc

1 4 4 c

2 cba

Output

6

5

Note

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*.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/17/2021 07:11:19 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|