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 maxn = 1e+5 + 400;
const int maxs = 700 + 10;
int n, m, s, qq;
char str[maxn], a[maxn];
int nxt[maxn];
struct SAM {
  int ch[maxs][26], mx[maxs], pr[maxs];
  int rd[maxs], Rsiz[maxs], last, tot;
  void clear() {
    tot = Rsiz[0] = 1;
    pr[0] = -1;
    last = mx[0] = rd[0] = 0;
    memset(ch, -1, sizeof(ch));
  }
  void extend(char c) {
    int p = last, np = last = tot++;
    mx[np] = mx[p] + 1;
    Rsiz[np] = 1;
    rd[np] = 0;
    for (; p != -1 && ch[p][c - 'a'] == -1; p = pr[p]) ch[p][c - 'a'] = np;
    if (p == -1) {
      pr[np] = 0;
      rd[0]++;
      return;
    }
    int q = ch[p][c - 'a'];
    if (mx[q] == mx[p] + 1) {
      pr[np] = q;
      rd[q]++;
      return;
    }
    int nq = tot++;
    rd[nq] = 2;
    Rsiz[nq] = 0;
    mx[nq] = mx[p] + 1;
    pr[nq] = pr[q];
    pr[q] = pr[np] = nq;
    for (int i = 0; i < 26; i++) ch[nq][i] = ch[q][i];
    for (; p != -1 && ch[p][c - 'a'] == q; p = pr[p]) ch[p][c - 'a'] = nq;
  }
  void calRsiz() {
    queue<int> q;
    int i, u;
    for (i = 0; i < tot; i++)
      if (!rd[i]) q.push(i);
    while (!q.empty()) {
      u = q.front();
      q.pop();
      Rsiz[pr[u]] += Rsiz[u];
      rd[pr[u]]--;
      if (!rd[pr[u]]) q.push(pr[u]);
    }
  }
  int find(char *s, int n) {
    int i, u = 0;
    for (i = 0; i < n; i++) {
      u = ch[u][s[i] - 'a'];
      if (u == -1) return 0;
    }
    return Rsiz[u];
  }
  inline void rebuilt(char *s, int n) {
    clear();
    for (int i = 0; i < n; i++) extend(s[i]);
    calRsiz();
  }
} S[330];
void input() {
  int i;
  scanf("%s%d", str, &qq);
  n = strlen(str);
  s = sqrt(n);
  for (i = 0; i <= n / s; i++) S[i].rebuilt(str + i * s, min(n - i * s, s));
}
void kmp_pre(char *s, int n) {
  int i, j;
  nxt[0] = nxt[1] = 0;
  for (i = 1; i < n; i++) {
    for (j = nxt[i]; s[i] != s[j] && j; j = nxt[j])
      ;
    nxt[i + 1] = j + (s[i] == s[j]);
  }
}
int kmp(char *s, char *t, int n, int m) {
  int i, j = 0, ans = 0;
  for (i = 0; i < n; i++) {
    for (; s[i] != t[j] && j; j = nxt[j])
      ;
    if (s[i] == t[j]) j++;
    if (j == m) ans++, j = nxt[j];
  }
  return ans;
}
void solve() {
  int op, l, r, i;
  scanf("%d", &op);
  if (op == 1) {
    scanf("%d%s", &l, a);
    l--;
    str[l] = a[0];
    S[l / s].rebuilt(str + l / s * s, min(n - l / s * s, s));
  } else {
    scanf("%d%d%s", &l, &r, a);
    l--;
    r--;
    m = strlen(a);
    kmp_pre(a, m);
    if (l / s == r / s || l / s + 1 == r / s || m >= s) {
      printf("%d\n", kmp(str + l, a, r - l + 1, m));
      return;
    }
    int ans = kmp(str + l, a, (l / s + 1) * s + m - 1 - l, m) +
              kmp(str + r / s * s - m + 1, a, r - r / s * s + m, m);
    for (i = l / s + 1; i < r / s; i++)
      ans += S[i].find(a, m) +
             (i != l / s + 1 ? kmp(str + i * s - m + 1, a, m - 1 << 1, m) : 0);
    cout << ans << endl;
  }
}
int main() {
  input();
  while (qq--) solve();
  return 0;
}