Problem: Given a string s, process q queries, each having one of the following forms:

  * 1 i c — Change the i-th character in the string to c. 
  * 2 l r y — Consider the substring of s starting at position l and ending at position r. Output the number of times y occurs as a substring in it. 

Input

The first line of the input contains the string s (1 ≤ |s| ≤ 105) of lowercase English letters.

The second line contains an integer q (1 ≤ q ≤ 105) — the number of queries to process.

The next q lines describe the queries and may have one of the following forms:

  * 1 i c (1 ≤ i ≤ |s|) 
  * 2 l r y (1 ≤ l ≤ r ≤ |s|) 



c is a lowercase English letter and y is a non-empty string consisting of only lowercase English letters.

The sum of |y| over all queries of second type is at most 105.

It is guaranteed that there is at least one query of second type.

All strings are 1-indexed.

|s| is the length of the string s.

Output

For each query of type 2, output the required answer in a separate line.

Examples

Input

ababababa
3
2 1 7 aba
1 5 c
2 1 7 aba


Output

3
1


Input

abcdcbc
5
2 1 7 bc
1 4 b
2 4 7 bc
1 2 a
2 1 4 aa


Output

2
2
1

Note

Consider the first sample case. Initially, the string aba occurs 3 times in the range [1, 7]. Note that two occurrences may overlap. 

After the update, the string becomes ababcbaba and now aba occurs only once in the range [1, 7].

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int sa = 2 * 150 + 10;
const int LEN = 100010;
char s[LEN], sq[LEN], zstring[2 * LEN];
int z[2 * LEN];
string temps;
struct SuffixAutomaton {
  int edges[26][sa], link[sa], length[sa], isTerminal[sa], dp1[sa], last;
  int sz;
  SuffixAutomaton() {
    last = 0;
    sz = 0;
  }
  void set(int k) {
    for (int i = 0; i < 26; ++i) edges[i][k] = -1;
  }
  void build(string &s) {
    link[0] = -1;
    length[0] = 0;
    last = 0;
    sz = 1;
    set(0);
    for (int i = 0; i < s.size(); i++) {
      set(sz);
      length[sz] = i + 1;
      link[sz] = 0;
      int r = sz;
      ++sz;
      int p = last;
      while (p >= 0 && edges[s[i] - 'a'][p] == -1) {
        edges[s[i] - 'a'][p] = r;
        p = link[p];
      }
      if (p != -1) {
        int q = edges[s[i] - 'a'][p];
        if (length[p] + 1 == length[q]) {
          link[r] = q;
        } else {
          for (int i = 0; i < 26; ++i) {
            edges[i][sz] = edges[i][q];
          }
          length[sz] = length[p] + 1;
          link[sz] = link[q];
          int qq = sz;
          ++sz;
          link[q] = qq;
          link[r] = qq;
          while (p >= 0 && edges[s[i] - 'a'][p] == q) {
            edges[s[i] - 'a'][p] = qq;
            p = link[p];
          }
        }
      }
      last = r;
    }
    for (int i = 0; i < sz; ++i) isTerminal[i] = 0, dp1[i] = -1;
    int p = last;
    while (p > 0) {
      isTerminal[p] = 1;
      p = link[p];
    }
  }
  int solve(int pos) {
    if (dp1[pos] != -1) return dp1[pos];
    dp1[pos] = isTerminal[pos];
    for (int i = 0; i < 26; ++i) {
      if (edges[i][pos] != -1) dp1[pos] += solve(edges[i][pos]);
    }
    return dp1[pos];
  }
  int run() {
    int cur = 0;
    for (int i = 1; sq[i] != '\0'; ++i) {
      auto it = edges[sq[i] - 'a'][cur];
      if (it == -1)
        return 0;
      else
        cur = it;
    }
    return solve(cur);
  }
} SA[800];
void computeZ() {
  int l, r;
  z[0] = 0;
  l = r = -1;
  for (int i = 1; zstring[i] != '\0'; ++i) {
    z[i] = 0;
    if (r > i) {
      z[i] = min(z[i - l], r - i + 1);
    }
    while (zstring[i + z[i]] == zstring[z[i]]) ++z[i];
    if (i + z[i] - 1 > r) {
      r = i + z[i] - 1;
      l = i;
    }
  }
}
int computeBrute(int l, int r, int sqlen) {
  int zslen = 0, ans = 0;
  for (int i = 1; i <= sqlen; ++i) {
    zstring[zslen++] = sq[i];
  }
  zstring[zslen++] = '$';
  for (int i = l; i <= r; ++i) {
    zstring[zslen++] = s[i];
  }
  zstring[zslen] = '\0';
  computeZ();
  for (int i = 1; i < zslen; ++i) {
    if (z[i] >= sqlen) {
      ++ans;
    }
  }
  return ans;
}
int main() {
  int q, typ, l, r, slen;
  char ch;
  scanf(" %s", &s[1]);
  slen = strlen(&s[1]);
  scanf("%d", &q);
  for (int i = 0; i <= slen; i += 150) {
    temps = "";
    int tempr = min(i + 150 - 1, slen);
    for (int j = max(1, i); j <= tempr; ++j) {
      temps += s[j];
    }
    SA[i / 150].build(temps);
  }
  while (q--) {
    scanf("%d", &typ);
    if (typ == 1) {
      scanf("%d %c", &l, &ch);
      s[l] = ch;
      temps = "";
      int bkt = l / 150;
      int tempr = min(slen, (bkt + 1) * 150 - 1);
      for (int i = max(1, bkt * 150); i <= tempr; ++i) {
        temps += s[i];
      }
      SA[bkt].build(temps);
    } else {
      scanf("%d %d %s", &l, &r, &sq[1]);
      int sqlen = strlen(&sq[1]);
      if (sqlen >= 150 || r - l <= 2 * 150) {
        printf("%d\n", computeBrute(l, r, sqlen));
      } else {
        int lbkt = l / 150, rbkt = r / 150, ans = 0;
        for (int i = lbkt + 1; i < rbkt; ++i) {
          ans += SA[i].run();
        }
        ans += computeBrute(l, (lbkt + 1) * 150 - 1, sqlen);
        ans += computeBrute(rbkt * 150, r, sqlen);
        for (int i = lbkt + 1; i <= rbkt; ++i) {
          ans += computeBrute(max(l, i * 150 - sqlen + 1),
                              min(r, i * 150 + sqlen - 2), sqlen);
        }
        printf("%d\n", ans);
      }
    }
  }
  return 0;
}