Problem: 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 li to ri by a character ci. 
  2. 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: 

  1. Operation of the first type starts with 1 followed by a triple li, ri and ci, that denotes replacement of all characters at positions from li to ri by character ci (1 ≤ li ≤ ri ≤ n, ci is one of the first k lowercase English letters). 
  2. 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.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long long dx[8] = {0, 1, 0, -1, 1, 1, -1, -1};
long long dy[8] = {1, 0, -1, 0, -1, 1, 1, -1};
class pa3 {
 public:
  long long x;
  long long y, z;
  pa3(long long x = 0, long long y = 0, long long z = 0) : x(x), y(y), z(z) {}
  bool operator<(const pa3& p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    return z < p.z;
  }
  bool operator>(const pa3& p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    return z > p.z;
  }
  bool operator==(const pa3& p) const {
    return x == p.x && y == p.y && z == p.z;
  }
  bool operator!=(const pa3& p) const {
    return !(x == p.x && y == p.y && z == p.z);
  }
};
class pa4 {
 public:
  long long x;
  long long y, z, w;
  pa4(long long x = 0, long long y = 0, long long z = 0, long long w = 0)
      : x(x), y(y), z(z), w(w) {}
  bool operator<(const pa4& p) const {
    if (x != p.x) return x < p.x;
    if (y != p.y) return y < p.y;
    if (z != p.z) return z < p.z;
    return w < p.w;
  }
  bool operator>(const pa4& p) const {
    if (x != p.x) return x > p.x;
    if (y != p.y) return y > p.y;
    if (z != p.z) return z > p.z;
    return w > p.w;
  }
  bool operator==(const pa4& p) const {
    return x == p.x && y == p.y && z == p.z && w == p.w;
  }
};
class pa2 {
 public:
  long long x, y;
  pa2(long long x = 0, long long y = 0) : x(x), y(y) {}
  pa2 operator+(pa2 p) { return pa2(x + p.x, y + p.y); }
  pa2 operator-(pa2 p) { return pa2(x - p.x, y - p.y); }
  bool operator<(const pa2& p) const { return y != p.y ? y < p.y : x < p.x; }
  bool operator>(const pa2& p) const { return x != p.x ? x < p.x : y < p.y; }
  bool operator==(const pa2& p) const {
    return abs(x - p.x) == 0 && abs(y - p.y) == 0;
  }
  bool operator!=(const pa2& p) const {
    return !(abs(x - p.x) == 0 && abs(y - p.y) == 0);
  }
};
string itos(long long i) {
  ostringstream s;
  s << i;
  return s.str();
}
long long Gcd(long long v, long long b) {
  if (v == 0) return b;
  if (b == 0) return v;
  if (v > b) return Gcd(b, v);
  if (v == b) return b;
  if (b % v == 0) return v;
  return Gcd(v, b % v);
}
long long mod;
long long extgcd(long long a, long long b, long long& x, long long& y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = extgcd(b, a % b, y, x);
  y -= a / b * x;
  return d;
}
pair<long long, long long> operator+(const pair<long long, long long>& l,
                                     const pair<long long, long long>& r) {
  return {l.first + r.first, l.second + r.second};
}
pair<long long, long long> operator-(const pair<long long, long long>& l,
                                     const pair<long long, long long>& r) {
  return {l.first - r.first, l.second - r.second};
}
ostream& operator<<(ostream& os, const vector<long long>& VEC) {
  for (auto v : VEC) os << v << " ";
  return os;
}
ostream& operator<<(ostream& os, const pair<long long, long long>& PAI) {
  os << PAI.first << " : " << PAI.second;
  return os;
}
ostream& operator<<(ostream& os, const pa3& PAI) {
  os << PAI.x << " : " << PAI.y << " : " << PAI.z;
  return os;
}
ostream& operator<<(ostream& os, const pa4& PAI) {
  os << PAI.x << " : " << PAI.y << " : " << PAI.z << " : " << PAI.w;
  return os;
}
ostream& operator<<(ostream& os,
                    const vector<pair<long long, long long> >& VEC) {
  for (auto v : VEC) os << v << " ";
  return os;
}
long long beki(long long wa, long long rr, long long warukazu) {
  if (rr == 0) return 1 % warukazu;
  if (rr == 1) return wa % warukazu;
  wa %= warukazu;
  if (rr % 2 == 1)
    return ((long long)beki(wa, rr - 1, warukazu) * (long long)wa) % warukazu;
  long long zx = beki(wa, rr / 2, warukazu);
  return (zx * zx) % warukazu;
}
long long pr[1100000];
long long inv[1100000];
long long comb(long long nn, long long rr) {
  if (rr < 0 || rr > nn || nn < 0) return 0;
  long long r = pr[nn] * inv[rr];
  r %= mod;
  r *= inv[nn - rr];
  r %= mod;
  return r;
}
void gya(long long ert) {
  pr[0] = 1;
  for (long long i = 1; i <= ert; i++) {
    pr[i] = ((long long)pr[i - 1] * i) % mod;
  }
  inv[ert] = beki(pr[ert], mod - 2, mod);
  for (long long i = ert - 1; i >= 0; i--) {
    inv[i] = (long long)inv[i + 1] * (i + 1) % mod;
  }
}
struct seg_rangeupd_getsum {
 private:
 public:
  long long cor = (1 << 18);
  long long inff = 1000000007 * 1000000ll;
  vector<long long> vec;
  vector<long long> lazy;
  void shoki1() {
    vec.resize(2 * cor + 3, 0);
    lazy.resize(2 * cor + 3, inff);
  }
  void shoki2() {}
  long long chien(long long k, long long len) {
    if (lazy[k] == inff) return vec[k];
    if (k < cor) {
      vec[k] = lazy[k] * len;
      lazy[2 * k] = lazy[k];
      lazy[2 * k + 1] = lazy[k];
      lazy[k] = inff;
    } else {
      vec[k] = lazy[k];
      lazy[k] = inff;
    }
    return vec[k];
  }
  void clear_chien(long long r) {
    if (r == 0) return;
    long long f = 31 - __builtin_clz(r);
    long long pos = 0;
    long long len = cor;
    for (long long i = f; i >= 0; i--) {
      pos *= 2;
      pos += !!(r & (1 << i));
      chien(pos, len);
      len /= 2;
    }
  }
  void rangeupd(long long a, long long b, long long w) {
    a += cor, b += cor;
    long long aa = a / (a & (-a)) / 2;
    long long bb = b / (b & (-b)) / 2;
    long long lenaa = 2 * (a & -a);
    long long lenbb = 2 * (b & -b);
    clear_chien(aa);
    clear_chien(bb);
    while (a < b) {
      if (a & 1) {
        lazy[a] = w;
        a++;
      }
      if (b & 1) {
        b--;
        lazy[b] = w;
      }
      a /= 2, b /= 2;
    }
    while (aa > 0 || bb > 0) {
      if (aa > bb) {
        vec[aa] = chien(2 * aa, lenaa / 2) + chien(2 * aa + 1, lenaa / 2);
        aa /= 2;
        lenaa *= 2;
      } else if (aa < bb) {
        vec[bb] = chien(2 * bb, lenbb / 2) + chien(2 * bb + 1, lenbb / 2);
        bb /= 2;
        lenbb *= 2;
      } else {
        vec[aa] = chien(2 * aa, lenaa / 2) + chien(2 * aa + 1, lenaa / 2);
        aa /= 2;
        lenaa *= 2;
        bb = aa, lenbb = aa;
      }
    }
  }
  long long getsum(long long a, long long b) {
    a += cor, b += cor;
    long long aa = a / (a & (-a)) / 2;
    long long bb = b / (b & (-b)) / 2;
    clear_chien(aa);
    clear_chien(bb);
    long long ans = 0;
    long long len = 1;
    while (a < b) {
      if (a & 1) {
        ans += chien(a, len);
        a++;
      }
      if (b & 1) {
        b--;
        ans += chien(b, len);
      }
      a /= 2, b /= 2, len *= 2;
    }
    return ans;
  }
  long long lower_bound(long long p, long long x) {
    p += cor;
    long long ima = 0;
    bool fst = 1;
    long long len = 1;
    while (1) {
      while (!(p & 1)) p /= 2, len *= 2;
      if (fst) fst = 0, clear_chien(p / 2);
      if (ima + chien(p, len) >= x) break;
      ima = ima + vec[p];
      p++;
      if (p == (p & (-p))) return cor;
    }
    while (1) {
      if (p >= cor) return p - cor;
      p *= 2;
      len /= 2;
      if (ima + chien(p, len) < x) {
        ima += vec[p];
        p++;
      }
    }
  }
  long long upper_bound(long long p, long long x) {
    p += cor;
    long long ima = 0;
    bool fst = 1;
    long long len = 1;
    while (1) {
      while (!(p & 1)) p /= 2, len *= 2;
      if (fst) fst = 0, clear_chien(p / 2);
      if (ima + chien(p, len) > x) break;
      ima = ima + vec[p];
      p++;
      if (p == (p & (-p))) return cor;
    }
    while (1) {
      if (p >= cor) return p - cor;
      p *= 2;
      len /= 2;
      if (ima + chien(p, len) <= x) {
        ima += vec[p];
        p++;
      }
    }
  }
};
void solve() {
  long long n, q, t;
  cin >> n >> q >> t;
  string s;
  cin >> s;
  seg_rangeupd_getsum ss;
  ss.shoki1();
  ss.shoki2();
  for (long long i = 0; i < n; i++) {
    ss.rangeupd(i, i + 1, s[i] - 'a');
  }
  set<long long> se;
  long long dp[11][11] = {};
  for (long long i = 0; i < n - 1; i++) {
    if (s[i] != s[i + 1]) {
      se.insert(i);
      dp[s[i] - 'a'][s[i + 1] - 'a']++;
    }
  }
  se.insert(1000000007);
  while (q--) {
    long long e;
    cin >> e;
    if (e == 1) {
      long long l, r;
      char c;
      cin >> l >> r >> c;
      l--;
      auto it = se.lower_bound(l - 1);
      while (1) {
        if (*it >= r) break;
        long long mae = ss.getsum(*it, *it + 1);
        long long ato = ss.getsum(*it + 1, *it + 2);
        dp[mae][ato]--;
        it = se.erase(it);
      }
      ss.rangeupd(l, r, c - 'a');
      if (l) {
        long long mae = ss.getsum(l - 1, l);
        long long ato = ss.getsum(l, l + 1);
        if (mae != ato) dp[mae][ato]++, se.insert(l - 1);
      }
      if (r < n) {
        long long mae = ss.getsum(r - 1, r);
        long long ato = ss.getsum(r, r + 1);
        if (mae != ato) dp[mae][ato]++, se.insert(r - 1);
      }
    } else {
      string w;
      cin >> w;
      long long ans = n;
      for (long long i = 0; i < t; i++)
        for (long long j = i + 1; j < t; j++) {
          ans -= dp[w[i] - 'a'][w[j] - 'a'];
        }
      cout << ans << endl;
    }
  }
}
signed main() {
  mod = 1000000007;
  cin.tie(0);
  ios::sync_with_stdio(false);
  long long n = 1;
  for (long long i = 0; i < n; i++) solve();
  return 0;
}