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
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def binary_trie():
    G0, G1, cnt = [-1], [-1], [0]
    return G0, G1, cnt

def insert(x, l):
    j = 0
    for i in range(l, -1, -1):
        cnt[j] += 1
        if x & pow2[i]:
            if G1[j] == -1:
                G0.append(-1)
                G1.append(-1)
                cnt.append(0)
                G1[j] = len(cnt) - 1
            j = G1[j]
        else:
            if G0[j] == -1:
                G0.append(-1)
                G1.append(-1)
                cnt.append(0)
                G0[j] = len(cnt) - 1
            j = G0[j]
    cnt[j] += 1
    return

def erase(x, l):
    j = 0
    for i in range(l, -1, -1):
        cnt[j] -= 1
        if x & pow2[i]:
            j = G1[j]
        else:
            j = G0[j]
    cnt[j] -= 1
    return

def kth_min(k, l):
    j = 0
    ans = 0
    for i in range(l, -1, -1):
        if not G0[j] == -1 and cnt[G0[j]] >= k:
            j = G0[j]
        else:
            ans += pow2[i]
            if not G0[j] == -1:
                k -= cnt[G0[j]]
            j = G1[j]
    return ans

def count_min(k, l):
    j = 0
    ans = 0
    for i in range(l, -1, -1):
        if k & pow2[i]:
            if G0[j] ^ -1:
                ans += cnt[G0[j]]
            j = G1[j]
        else:
            j = G0[j]
    return ans

def f(u, v):
    return u * k + v

n, m, k = map(int, input().split())
s = list(input().rstrip())
s = [-1] + [i - 97 for i in s]
G0, G1, cnt = binary_trie()
l = 20
pow2 = [1]
for _ in range(l):
    pow2.append(2 * pow2[-1])
u = [1]
r = [-1] * (n + 1)
for i in range(2, n + 1):
    if s[i] ^ s[i - 1]:
        r[u[-1]] = i - 1
        u.append(i)
r[u[-1]] = n
for i in range(1, n + 1):
    if r[i] ^ -1:
        insert(i, l)
k2 = k * k
cnt0 = [0] * k2
for i in range(1, n):
    cnt0[f(s[i], s[i + 1])] += 1
ans = []
for _ in range(m):
    t = list(input().rstrip().decode().split())
    if t[0] == "1":
        l0, r0, c = int(t[1]), int(t[2]), ord(t[3]) - 97
        k0 = count_min(l0 + 1, l)
        x = kth_min(k0, l)
        v = [x]
        while r[v[-1]] + 1 <= r0:
            v.append(r[v[-1]] + 1)
        for i in range(len(v) - 1):
            cnt0[f(s[v[i]], s[v[i + 1]])] -= 1
        for i in v:
            li, ri = max(i, l0), min(r[i], r0)
            cnt0[f(s[i], s[i])] -= ri - li
        if v[0] ^ l0:
            cnt0[f(s[v[0]], s[v[0]])] -= 1
        elif v[0] ^ 1:
            cnt0[f(s[kth_min(k0 - 1, l)], s[v[0]])] -= 1
        if r[v[-1]] ^ r0:
            cnt0[f(s[v[-1]], s[v[-1]])] -= 1
        elif r[v[-1]] ^ n:
            cnt0[f(s[v[-1]], s[r0 + 1])] -= 1
        for l1 in v:
            r1 = r[l1]
            if l0 <= l1:
                erase(l1, l)
            else:
                r[l1] = l0 - 1
            if r0 < r1:
                insert(r0 + 1, l)
                s[r0 + 1], r[r0 + 1] = s[l1], r1
        insert(l0, l)
        s[l0], r[l0] = c, r0
        cnt0[f(c, c)] += r0 - l0
        k0 = count_min(l0 + 1, l)
        if l0 ^ 1:
            cnt0[f(s[kth_min(k0 - 1, l)], c)] += 1
        if r0 ^ n:
            cnt0[f(c, s[kth_min(k0 + 1, l)])] += 1
    else:
        p = [ord(i) - 97 for i in t[1]]
        ans0 = 1
        for i in range(k):
            for j in range(i, k):
                ans0 += cnt0[f(p[i], p[j])]
        ans.append(ans0)
sys.stdout.write("\n".join(map(str, ans)))