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;
using ll = long long;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;
const int N = 1565;
using ull = unsigned long long;
struct Bitset {
  ull b[N];
  Bitset() { reset(); }
  void set() { memset(b, 0xff, sizeof b); }
  void set(int k) { b[k >> 6] |= 1LL << (k & 63); }
  void reset() { memset(b, 0, sizeof b); }
  void reset(int k) { b[k >> 6] &= ~(1LL << (k & 63)); }
  bool get(int k) { return (b[k >> 6] >> (k & 63)) & 1; }
  Bitset operator<<(int k) {
    if (k == 0) return *this;
    Bitset ret;
    int pos = (k + 63) >> 6, s = (k & 63), t = (64 - s) & 63;
    for (int i = 0; pos <= N; i++, pos++) {
      if (pos < N) ret.b[i] = b[pos] << t;
      if (s) ret.b[i] |= (b[pos - 1]) >> s;
    }
    return ret;
  }
  void operator&=(const Bitset& o) {
    for (int i = 0; i < N; i++) b[i] &= o.b[i];
  }
  int count(int l, int r) {
    int pl = l >> 6, pr = r >> 6;
    if (pl == pr) {
      int s = l & 63, d = r - l + 1;
      return __builtin_popcountll((b[pl] >> s) & (((ull)1 << d) - 1));
    }
    int s = l & 63, t = r & 63;
    int ans = __builtin_popcountll((b[pl] >> s));
    for (int i = pl + 1; i < pr; i++) ans += __builtin_popcountll(b[i]);
    if (t == 63) return ans + __builtin_popcountll(b[pr] & UINT64_MAX);
    return ans + __builtin_popcountll(b[pr] & (((ull)1 << (t + 1)) - 1));
  }
  void output(int k) {
    for (int i = 0; i < k; i++) cout << get(i);
    cout << "\n";
  }
} b[26], ans;
string s, t;
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cin >> s;
  int n = s.size(), q;
  for (int i = 0; i <= n - 1; i++) {
    b[s[i] - 'a'].set(i);
  }
  cin >> q;
  while (q--) {
    int op, l, r, pos;
    char c;
    cin >> op;
    if (op == 1) {
      cin >> pos >> c;
      pos--;
      b[s[pos] - 'a'].reset(pos);
      s[pos] = c;
      b[c - 'a'].set(pos);
    } else {
      cin >> l >> r >> t;
      int m = t.size();
      if (r - l + 1 < m) {
        cout << 0 << "\n";
        continue;
      }
      l--;
      r--;
      ans = b[t[0] - 'a'];
      for (int i = 1; i < m; i++) {
        ans &= (b[t[i] - 'a'] << i);
      }
      cout << ans.count(l, r - m + 1) << "\n";
    }
  }
  return 0;
}