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*<sub class="lower-index">*i*</sub> to *r*<sub class="lower-index">*i*</sub> by a character *c*<sub class="lower-index">*i*</sub>. 1.  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.
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*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> and *c*<sub class="lower-index">*i*</sub>, that denotes replacement of all characters at positions from *l*<sub class="lower-index">*i*</sub> to *r*<sub class="lower-index">*i*</sub> by character *c*<sub class="lower-index">*i*</sub> (1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*, *c*<sub class="lower-index">*i*</sub> is one of the first *k* lowercase English letters). 1.  Operation of the second type starts with 2 followed by a permutation of the first *k* lowercase English letters.
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*.
7 4 3
abacaba
1 3 5 b
2 abc
1 4 4 c
2 cba
6
5
5 5 3
cbcab
1 2 4 b
2 cab
2 bca
1 2 3 a
1 2 2 c
4
5
10 10 3
cababcacaa
1 3 3 b
2 acb
2 abc
1 8 10 c
1 7 9 c
1 4 7 b
2 cba
1 5 6 a
1 9 9 c
2 acb
7
6
9
8
10 20 5
ebbbcebbea
1 5 9 a
1 1 2 b
2 abdce
2 edacb
2 ebdca
2 cdbae
1 4 9 d
1 1 3 b
1 4 9 e
1 5 9 b
2 cbeda
1 10 10 c
1 6 9 a
1 3 4 c
1 2 3 b
2 aebdc
1 3 9 c
1 2 4 b
1 3 8 b
1 6 10 e
10
10
9
9
8
8

 #include <bits/stdc++.h>
using namespace std;

const int MAXN = (1<<18); 

int seg [MAXN << 2][10][10]; 
int lazy [MAXN << 2]; 
int l [4 * MAXN], r [4 * MAXN]; 
char s[MAXN];
int n, m, k; 
 
void build (int start, int end, int node){
    if (start == end){
        l[node] = s[start] - 'a'; 
        r[node] = s[start] - 'a'; 
        return; 
    }
    build (start, (start+end)/2, 2*node), build ((start+end)/2+1, end, 2*node+1); 
    l[node] = l[2*node], r[node] = r[2*node+1]; 
    for (int g=0; g<k; g++) for (int y=0; y<k; y++) seg[node][g][y]=seg[2*node][g][y]+seg[2*node+1][g][y]; 
    seg[node][r[2*node]][l[2*node+1]]++; 
}

void push (int start, int end, int node){
    if (lazy[node]>-1){
        if (start<end) lazy[2*node] = lazy[2*node+1] = lazy[node]; 
        l[node] = r[node] = lazy[node]; 
        memset (seg[node], 0, sizeof(seg[node])); seg[node][lazy[node]][lazy[node]]=end-start; 
        lazy[node] = -1; 
    }
}   

void update (int start, int end, int i, int j, int node, int v){
    push(start, end, node); 
    if (start>j||end<i) return; 
    if (start>=i && end<=j){
        lazy[node] = v; push(start,end,node); return; 
    }
    update (start, (start+end)/2,i,j,2*node,v),update((start+end)/2+1,end,i,j,2*node+1,v); 
    l[node] = l[2*node], r[node] = r[2*node+1]; 
    for (int g=0; g<k; g++) for (int y=0; y<k; y++) seg[node][g][y]=seg[2*node][g][y]+seg[2*node+1][g][y]; 
    seg[node][r[2*node]][l[2*node+1]]++; 
}

int main(){
    memset(lazy,-1,sizeof(lazy)); 
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m >> k; 
    for (int g=1; g<=n; g++) cin >> s[g]; 
    
    build (1, n, 1); 
    
    for (int g=0; g<m; g++){
        int t;
        cin >> t;
        if (t == 1){
            int l, r;
            cin >> l >> r;
            char k; 
            cin >> k; 
            update (1, n, l, r, 1, k-'a'); 
        }
        else{
            int ans = 1;
            string x; cin >> x;
            for (int y=0; y<x.length(); y++){
                for (int z=y; z<x.length(); z++){
                    ans+=seg[1][x[z]-'a'][x[y]-'a']; 
                }
            }
            cout << ans << '\n';
        }
    }    
    return 0; 
}