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 dr[]{-1, -1, 0, 1, 1, 1, 0, -1};
const int dc[]{0, 1, 1, 1, 0, -1, -1, -1};
void run() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
}
const int sqrtQ = 350;
class suffix_array {
  const static int alpha = 128;
  int getOrder(int a) const { return (a < (int)order.size() ? order[a] : 0); }

 public:
  int n;
  string s;
  vector<int> suf, order, lcp;
  suffix_array() {}
  suffix_array(const string &s) : n(s.size() + 1), s(s) {
    suf = order = lcp = vector<int>(n);
    vector<int> bucket_idx(n), newOrder(n), newsuff(n);
    {
      vector<int> prev(n), head(alpha, -1);
      for (int i = 0; i < n; i++) {
        prev[i] = head[s[i]];
        head[s[i]] = i;
      }
      int buc = -1, idx = 0;
      for (int i = 0; i < alpha; i++) {
        if (head[i] == -1) continue;
        bucket_idx[++buc] = idx;
        for (int j = head[i]; ~j; j = prev[j]) suf[idx++] = j, order[j] = buc;
      }
    }
    int len = 1;
    do {
      auto cmp = [&](int a, int b) {
        if (order[a] != order[b]) return order[a] < order[b];
        return getOrder(a + len) < getOrder(b + len);
      };
      for (int i = 0; i < n; i++) {
        int j = suf[i] - len;
        if (j < 0) continue;
        newsuff[bucket_idx[order[j]]++] = j;
      }
      for (int i = 1; i < n; i++) {
        suf[i] = newsuff[i];
        bool cmpres = cmp(suf[i - 1], suf[i]);
        newOrder[suf[i]] = newOrder[suf[i - 1]] + cmpres;
        if (cmpres) bucket_idx[newOrder[suf[i]]] = i;
      }
      order = newOrder;
      len <<= 1;
    } while (order[suf[n - 1]] != n - 1);
  }
  int count(const string &x) {
    int st = 0, ed = n;
    for (int i = 0; i < (int)(x.size()) && st < ed; i++) {
      auto cmp = [&](int a, int b) {
        if (a == -1) return x[i] < s[b + i];
        return s[a + i] < x[i];
      };
      st = lower_bound(suf.begin() + st, suf.begin() + ed, -1, cmp) -
           suf.begin();
      ed = upper_bound(suf.begin() + st, suf.begin() + ed, -1, cmp) -
           suf.begin();
    }
    return max(0, ed - st);
  }
} SA[(int)1e4];
string y;
vector<int> longestPrefix;
vector<int> Fail[26];
int fail(int k, char nxt) {
  int &rt = Fail[nxt - 'a'][k];
  if (~rt) return rt;
  while (k > 0 && y[k] != nxt) k = longestPrefix[k - 1];
  if (nxt == y[k]) k++;
  return rt = k;
}
void failure_function() {
  int n = y.size();
  longestPrefix = vector<int>(n);
  for (int i = 0; i < 26; i++) Fail[i] = vector<int>(n + 1, -1);
  for (int i = 1, k = 0; i < n; i++) longestPrefix[i] = k = fail(k, y[i]);
}
int main() {
  run();
  string s;
  int q;
  cin >> s >> q;
  for (int i = 0; i < (int)(s.size()); i += sqrtQ)
    SA[i / sqrtQ] = suffix_array(s.substr(i, sqrtQ));
  auto solve = [&](int l, int r) {
    int match = 0, cnt = 0;
    for (int i = l; i <= r; i++) {
      match = fail(match, s[i]);
      if (match == (int)(y.size())) {
        cnt++;
        match = longestPrefix[match - 1];
      }
    }
    return cnt;
  };
  while (q--) {
    int t;
    cin >> t;
    if (t == 1) {
      int idx;
      char ch;
      cin >> idx >> ch;
      idx--;
      s[idx] = ch;
      SA[idx / sqrtQ] = suffix_array(s.substr(idx / sqrtQ * sqrtQ, sqrtQ));
    } else {
      int l, r;
      cin >> l >> r >> y;
      l--, r--;
      failure_function();
      if ((int)(y.size()) >= sqrtQ || r - l <= 2 * sqrtQ) {
        cout << solve(l, r) << "\n";
        continue;
      }
      int ans = 0, len = (int)(y.size());
      int st = l / sqrtQ, ed = r / sqrtQ;
      ans += solve(l, (st + 1) * sqrtQ + len - 2);
      ans += solve(ed * sqrtQ - len + 1, r);
      for (int i = st + 1; i < ed; i++) ans += SA[i].count(y);
      for (int i = st + 2; i < ed; i++)
        ans += solve(i * sqrtQ - len + 1, i * sqrtQ + len - 2);
      cout << ans << "\n";
    }
  }
}