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;
inline int getint() {
  char c = getchar();
  int res = 0, f = 1;
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    res = res * 10 + c - '0';
    c = getchar();
  }
  return res * f;
}
const int maxn = 3e5 + 10;
char s[maxn], t[maxn];
int n, m, T, tlen, nod[maxn];
int vis[maxn], tmp[maxn], c[maxn], p[maxn], top;
int fa[maxn], Max[maxn], cnt[maxn], tot, last;
int ch[maxn][30];
vector<int> E[maxn];
queue<int> Q;
int f[maxn];
long long ans;
inline int newnode() {
  int o;
  if (Q.empty())
    o = ++tot;
  else {
    o = Q.front();
    Q.pop();
    Max[o] = vis[o] = cnt[o] = fa[o] = 0;
    memset(ch[o], 0, sizeof(ch[o]));
  }
  return p[++top] = o;
}
inline void insert(int c, int rt) {
  int v = last;
  Max[last = newnode()] = Max[v] + 1;
  fa[last] = rt;
  while (v && !ch[v][c]) ch[v][c] = last, v = fa[v];
  if (!v) return;
  int p = ch[v][c];
  if (Max[p] != Max[v] + 1) {
    int np = newnode();
    Max[np] = Max[v] + 1;
    fa[np] = fa[p];
    fa[p] = fa[last] = np;
    while (v && ch[v][c] == p) ch[v][c] = np, v = fa[v];
    for (int i = (1); i <= (26); i++) ch[np][i] = ch[p][i];
  } else
    fa[last] = p;
}
inline void dfs(int u) {
  if (vis[u]) return;
  vis[u] = 1;
  Q.push(u);
  for (int i = (1); i <= (26); i++)
    if (ch[u][i]) dfs(ch[u][i]);
}
inline void build(int id) {
  if (nod[id]) dfs(nod[id]);
  nod[id] = last = newnode();
  int l = (id - 1) * T + 1, r = min(id * T, n);
  for (int i = (l); i <= (r); i++)
    insert(s[i] - 'a' + 1, nod[id]), cnt[last] = 1;
  int see = 0;
  for (int i = (1); i <= (top); i++) see = max(see, Max[p[i]]);
  for (int i = (0); i <= (top); i++) c[i] = 0;
  for (int i = (1); i <= (top); i++) c[Max[p[i]]]++;
  for (int i = (1); i <= (top); i++) c[i] += c[i - 1];
  for (int i = (top); i >= (1); i--) tmp[c[Max[p[i]]]--] = p[i];
  for (int i = (top); i >= (1); i--) cnt[fa[tmp[i]]] += cnt[tmp[i]];
  top = 0;
}
inline void init() {
  f[1] = f[0] = 0;
  for (int i = (2); i <= (tlen); i++) {
    f[i] = f[i - 1];
    while (f[i] && t[f[i] + 1] != t[i]) f[i] = f[f[i]];
    f[i] = t[f[i] + 1] == t[i] ? f[i] + 1 : 0;
  }
}
inline void kmp(int l, int r) {
  if (r - l + 1 < tlen) return;
  int now = 0;
  for (int i = (l); i <= (r); i++) {
    while (now && t[now + 1] != s[i]) now = f[now];
    now = t[now + 1] == s[i] ? now + 1 : 0;
    if (now == tlen) ans++;
  }
}
inline void calc(int id) {
  int o = nod[id];
  for (int i = (1); i <= (tlen); i++) {
    o = ch[o][t[i] - 'a' + 1];
    if (!o) return;
  }
  ans += cnt[o];
}
inline void getans(int l, int r) {
  ans = 0;
  init();
  if (tlen <= T) {
    int lid = (l + T - 1) / T, rid = (r + T - 1) / T;
    if (lid == rid)
      kmp(l, r);
    else {
      for (int j = (lid + 1); j <= (rid - 1); j++) calc(j);
      for (int j = (lid); j <= (rid - 1); j++)
        kmp(max(j * T - tlen + 2, l), min(j * T + tlen - 1, r));
      kmp(l, lid * T);
      kmp((rid - 1) * T + 1, r);
    }
  } else
    kmp(l, r);
}
int main() {
  T = 150;
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i = (1); i <= ((n + T - 1) / T); i++) build(i);
  m = getint();
  while (m--) {
    int typ = getint();
    if (typ == 1) {
      int pos = getint();
      s[pos] = getchar();
      build((pos + T - 1) / T);
    } else {
      int l = getint(), r = getint();
      scanf("%s", t + 1);
      tlen = strlen(t + 1);
      getans(l, r);
      printf("%lld\n", ans);
    }
  }
  return 0;
}