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;
int dy[] = {1, -1, 0, 0, -1, 1, 1, -1};
int dx[] = {0, 0, 1, -1, 1, -1, 1, -1};
void file() {}
void fast() {
  std::ios_base::sync_with_stdio(0);
  cin.tie(NULL);
}
const int N = 1e5 + 9;
char s[N], y[N];
class SuffixAutomaton {
 private:
  class SNode {
   public:
    int len, link, firstpos, is_clone;
    vector<int> next;
    int endpos;
    vector<int> inv_next;
    SNode() {
      len = 0, link = firstpos = -1;
      endpos = 1;
      is_clone = 0;
      next = vector<int>(26, -2);
    }
    SNode(const SNode& other) {
      len = other.len;
      link = other.link;
      next = other.next;
      firstpos = other.firstpos;
      endpos = other.endpos;
      is_clone = other.is_clone;
    }
  };

 public:
  int last, cur, n;
  vector<SNode> nodes;
  vector<long long> dist_substr;
  vector<int> sz_link_tree;
  SuffixAutomaton() {}
  SuffixAutomaton(int l, int r) {
    n = r - l + 1;
    nodes.resize(2 * n);
    dist_substr = vector<long long>(2 * n, -1);
    sz_link_tree = vector<int>(2 * n);
    last = 0, cur = 1;
    for (int i = l; i <= r; i++) add_char(s[i]);
    build_inv_next();
    dfs_linktree(0);
  }
  inline void add_char(char ch) {
    int newNode = cur++;
    nodes[newNode].len = nodes[last].len + 1;
    nodes[newNode].firstpos = nodes[newNode].len - 1;
    int p = last;
    last = newNode;
    for (; p != -1 && nodes[p].next[ch - 'a'] == -2; p = nodes[p].link)
      nodes[p].next[ch - 'a'] = newNode;
    if (p == -1) {
      nodes[newNode].link = 0;
      return;
    }
    int q = nodes[p].next[ch - 'a'];
    if (nodes[p].len + 1 == nodes[q].len) {
      nodes[newNode].link = q;
      return;
    }
    int clone = cur++;
    nodes[clone] = SNode(nodes[q]);
    nodes[clone].len = nodes[p].len + 1;
    nodes[clone].endpos = 0;
    nodes[clone].is_clone = true;
    nodes[q].link = clone;
    nodes[newNode].link = clone;
    for (; p != -1 && nodes[p].next[ch - 'a'] != -2 &&
           nodes[p].next[ch - 'a'] == q;
         p = nodes[p].link)
      nodes[p].next[ch - 'a'] = clone;
  }
  inline void build_inv_next() {
    for (int i = 1; i < cur; i++) nodes[nodes[i].link].inv_next.push_back(i);
  }
  inline void dfs_linktree(int u) {
    sz_link_tree[u] = !nodes[u].is_clone;
    for (auto& v : nodes[u].inv_next) {
      dfs_linktree(v);
      sz_link_tree[u] += sz_link_tree[v];
    }
  }
  inline int match() {
    int u = 0, idx = 0;
    while (y[idx] != '\0' && nodes[u].next[y[idx] - 'a'] != -2)
      u = nodes[u].next[y[idx] - 'a'], idx++;
    if (y[idx] != '\0') return 0;
    return u;
  }
  inline int get_cnt_occurrences_of_pattern() {
    int u = match();
    if (!u) return 0;
    return sz_link_tree[u];
  }
};
int szy;
SuffixAutomaton sa[(int)1e5 + 9];
vector<int> f;
inline vector<int> failure() {
  f = vector<int>(szy);
  for (int i = 1; y[i] != '\0'; i++) {
    int p = f[i - 1];
    char ch = y[p];
    while (p && ch != y[i]) p = f[p - 1], ch = y[p];
    if (ch == y[i]) p++;
    f[i] = p;
  }
  return f;
}
inline int kmp(int l, int r) {
  int ret = 0;
  int idx = 0;
  for (int i = l; i <= r; i++) {
    if (s[i] == y[idx]) {
      idx++;
      if (y[idx] == '\0') {
        ret++;
        idx = f[idx - 1];
      }
      continue;
    }
    if (!idx) continue;
    idx = f[idx - 1];
    i--;
  }
  return ret;
}
const int sq = 100;
int main() {
  file();
  scanf(" %s", s);
  int n = strlen(s);
  int q;
  scanf("%d", &q);
  for (int i = 0; i * sq < n; i++)
    sa[i] = SuffixAutomaton(i * sq, min(n - 1, (i + 1) * sq - 1));
  while (q--) {
    int t;
    scanf("%d", &t);
    if (t == 1) {
      int i;
      char ch;
      scanf("%d %c", &i, &ch);
      i--;
      s[i] = ch;
      int bk = i / sq;
      sa[bk] = SuffixAutomaton(bk * sq, min(n - 1, (bk + 1) * sq - 1));
      continue;
    }
    int l, r;
    scanf("%d%d", &l, &r);
    l--, r--;
    scanf(" %s", y);
    szy = strlen(y);
    f = failure();
    if (szy >= sq || r - l + 1 <= 2 * sq) {
      printf("%d\n", kmp(l, r));
      continue;
    }
    int lbk = l / sq;
    int rbk = r / sq;
    int ans = kmp(l, (lbk + 1) * sq + szy - 2);
    ans += kmp(rbk * sq - szy + 1, r);
    for (int i = lbk + 1; i < rbk; i++)
      ans += sa[i].get_cnt_occurrences_of_pattern();
    for (int i = lbk + 1; i < rbk - 1; i++)
      ans += kmp((i + 1) * sq - szy + 1, (i + 1) * sq + szy - 2);
    printf("%d\n", ans);
  }
  return 0;
}