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 N = 1e5 + 5;
const int M = 405, C = N / M + 5;
char s[N];
int n, q, op, x, y;
char t[N];
int len;
struct sam {
  int son[M * 2][26], fa[M * 2], dep[M * 2], ed[M * 2], tot, la;
  void build() {
    for (int i = 1, _b = tot; i <= _b; i++) {
      memset(son[i], 0, sizeof son[i]);
      dep[i] = fa[i] = ed[i] = 0;
    }
    tot = la = 1;
  }
  void push(int v) { dep[++tot] = v; }
  void add(int c) {
    int p = la;
    push(dep[p] + 1);
    int np = tot;
    for (; p && !son[p][c]; p = fa[p]) son[p][c] = np;
    if (!p)
      fa[np] = 1;
    else {
      int q = son[p][c];
      if (dep[p] + 1 < dep[q]) {
        push(dep[p] + 1);
        int nq = tot;
        memcpy(son[nq], son[q], sizeof son[q]);
        fa[nq] = fa[q];
        fa[q] = fa[np] = nq;
        for (; son[p][c] == q; p = fa[p]) son[p][c] = nq;
      } else
        fa[np] = q;
    }
    la = np;
    ed[la] = 1;
  }
  int d[M * 2], d0, r[M * 2], f[M * 2];
  void dg(int x) {
    if (x == 1) d0 = 0;
    for (int i = 1, _b = d0; i <= _b; i++) putchar(d[i] + 'a');
    printf("\n");
    for (int j = 0, _b = 25; j <= _b; j++)
      if (son[x][j]) {
        d[++d0] = j;
        dg(son[x][j]);
        d0--;
      }
  }
  void work() {
    for (int i = 1, _b = tot; i <= _b; i++) r[i] = f[i] = 0;
    for (int i = 2, _b = tot; i <= _b; i++) r[fa[i]]++;
    d0 = 0;
    for (int i = 1, _b = tot; i <= _b; i++)
      if (!r[i]) d[++d0] = i;
    for (int i = 1; i <= tot - 1; i++) {
      int x = d[i];
      if (!(--r[fa[x]])) d[++d0] = fa[x];
      f[x] += ed[x], f[fa[x]] += f[x];
    }
  }
  int qry() {
    int p = 1;
    for (int i = 1, _b = len; i <= _b; i++) p = son[p][t[i] - 'a'];
    return f[p];
  }
} a[C];
int id[N], id0, il[C], ir[C];
void build(int i) {
  a[i].build();
  for (int j = il[i], _b = ir[i]; j <= _b; j++) a[i].add(s[j] - 'a');
  a[i].work();
}
int nt[N];
void get_nt() {
  int x = 0;
  for (int i = 2, _b = len; i <= _b; i++) {
    while (x && t[x + 1] != t[i]) x = nt[x];
    x += (t[x + 1] == t[i]);
    nt[i] = x;
  }
}
int qry(int l, int r, int z) {
  if (z != -1) {
    r = min(r, z + len - 2);
    l = max(l, z - len);
  }
  int ans = 0;
  int x = 0;
  for (int i = l, _b = r; i <= _b; i++) {
    while (x && t[x + 1] != s[i]) x = nt[x];
    x += (t[x + 1] == s[i]);
    if (x == len) {
      if (z == -1)
        ans++;
      else {
        if (i >= z && i - len + 1 < z) ans++;
      }
    }
  }
  return ans;
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i = 1, _b = n; i <= _b; i++) {
    if (i % M == 1) il[++id0] = i;
    id[i] = id0;
    ir[id0] = i;
  }
  for (int i = 1, _b = id0; i <= _b; i++) {
    build(i);
  }
  scanf("%d", &q);
  for (int ii = 1, _b = q; ii <= _b; ii++) {
    scanf("%d", &op);
    if (op == 1) {
      scanf("%d", &x);
      scanf("%s", t + 1);
      len = strlen(t + 1);
      s[x] = t[1];
      build(id[x]);
    } else {
      scanf("%d %d", &x, &y);
      scanf("%s", t + 1);
      len = strlen(t + 1);
      int ans = 0;
      if (len > M) {
        get_nt();
        ans = qry(x, y, -1);
      } else {
        int l = id[x], r = id[y];
        for (int i = l + 1, _b = r - 1; i <= _b; i++) ans += a[i].qry();
        get_nt();
        if (id[x] != id[y]) {
          ans += qry(x, ir[id[x]], -1);
          ans += qry(il[id[y]], y, -1);
          for (int i = l + 1, _b = r; i <= _b; i++)
            ans += qry((i - 1) == l ? x : il[i - 1], i == r ? y : ir[i], il[i]);
        } else {
          ans += qry(x, y, -1);
        }
      }
      printf("%d\n", ans);
    }
  }
}