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

input = lambda: sys.stdin.readline().rstrip("\r\n")
fast_print = lambda p: sys.stdout.write(str(p) + "\n") 

def merge(s1, s2):
  if not s1:
    return s2
  if not s2:
    return s1
  ll, lr, lc = s1
  rl, rr, rc = s2
  nl = ll
  nr = rr
  nc = [[lc[a][b] + rc[a][b] for b in range(k)] for a in range(k)]
  nc[lr][rl] += 1
  return nl, nr, nc

def default(char):
  converted = ord(char) - ord("a")
  c = [[0] * k for row in range(k)]
  return converted, converted, c

def make_lazy_segment_tree(arr):
  N = len(arr)
  size = 1 << (N-1).bit_length()
  tree = [None] * (2*size)
  lazy = [-1] * (2*size)
  for i in range(N):
    tree[size+i] = default(arr[i]) 
  for i in range(size-1,0,-1):
    tree[i] = merge(tree[2*i], tree[2*i+1])
  return tree, lazy

def update(tree, v, val):
  _, _, c = tree[v]
  nc = [[0 for b in range(k)] for a in range(k)]
  nc[val][val] = sum(sum(row) for row in c)
  tree[v] = (val, val, nc)

def push(tree, lazy, v):
  if lazy[v] == -1:
    return
  update(tree, 2*v, lazy[v])
  lazy[2*v] = lazy[v]
  update(tree, 2*v + 1, lazy[v])
  lazy[2*v+1] = lazy[v]
  lazy[v] = -1

def adjust(tree, lazy, v):
  # print(f"adjust called with {v}")
  v >>= 1
  while v:
    # print(f"      first v = {v}, {tree[v]}")
    if lazy[v] == -1:
      tree[v] = merge(tree[2*v], tree[2*v+1])
    # print(f"      now v = {v}, {tree[v]}")
    
    v >>= 1

def range_assign(tree, lazy, l, r, val):
  l += len(tree) >> 1
  r += (len(tree) >> 1) + 1
  old_l, old_r = l, r

  for i in range(l.bit_length()-1, 0, -1):
    push(tree, lazy, l >> i)
  for i in range((r-1).bit_length()-1,0,-1):
    push(tree, lazy, (r-1) >> i)

  while l < r:
    if l & 1:
      # print(f"(l)  time to update tree[{l}] from {tree[l]} to ")
      update(tree, l, val)
      # print(f"                          {tree[l]}")
      lazy[l] = val
      l += 1
    if r & 1:
      r -= 1
      # print(f"(r)  time to update tree[{r}] from {tree[r]} to ")
      update(tree, r, val)
      # print(f"                                {tree[r]}")
      lazy[r] = val
    l >>= 1
    r >>= 1
  adjust(tree, lazy, old_l)
  adjust(tree, lazy, old_r-1)

def total_sum(tree, lazy, l, r, perm):
  # for i in range(l.bit_length()-1, 0, -1):
  #   push(tree, lazy, l >> i)
  # for i in range((r-1).bit_length()-1,0,-1):
  #   push(tree, lazy, (r-1) >> i)


  perm_index = [0] * k
  for i, ele in enumerate(perm):
    perm_index[ele] = i
  dc = tree[1][2]
  total = 1
  for i in range(k):
    for j in range(k):
      if perm_index[i] <= perm_index[j]:
        total += dc[i][j]
  return total

n, m, k = [int(component) for component in input().split(" ")]
# print(n, m, k)
s = input()
# print(s)
tree, lazy = make_lazy_segment_tree(s)

# print(f"tree = {tree}")
# print(f"lazy = {lazy}")

def pp(tree):
  for node in range(1, len(tree)):
    print(f"node = {node}")
    if tree[node]:
      print(f"  l = {tree[node][0]}, r = {tree[node][1]}, c = {tree[node][2]}")
  
for _ in range(m):
  op_args = input().split()
  # print(f"op_args = {op_args}")
  if len(op_args) == 4:
    l, r, c = int(op_args[1]), int(op_args[2]), op_args[3]  
    # print(f"before tree")
    # pp(tree)
    range_assign(tree, lazy, l-1, r-1, ord(c) - ord("a"))
    # print(f"after tree")
    # pp(tree)
    # print(f"lazy = {lazy}")
    # break
  else:
    perm = [ord(c)-ord("a") for c in op_args[1]]
    print(total_sum(tree, lazy, 0, len(s)-1, perm))
