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;
template <typename... As>
struct tpl : public std::tuple<As...> {
  using std::tuple<As...>::tuple;
  tpl() {}
  tpl(std::tuple<As...> const& b) { std::tuple<As...>::operator=(b); }
  template <typename T = tuple<As...> >
  typename tuple_element<0, T>::type const& x() const {
    return get<0>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<0, T>::type& x() {
    return get<0>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<1, T>::type const& y() const {
    return get<1>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<1, T>::type& y() {
    return get<1>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<2, T>::type const& z() const {
    return get<2>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<2, T>::type& z() {
    return get<2>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<3, T>::type const& w() const {
    return get<3>(*this);
  }
  template <typename T = tuple<As...> >
  typename tuple_element<3, T>::type& w() {
    return get<3>(*this);
  }
};
using lli = int;
using llu = long long unsigned;
using pii = tpl<lli, lli>;
using piii = tpl<lli, lli, lli>;
using piiii = tpl<lli, lli, lli, lli>;
using vi = vector<lli>;
using vii = vector<pii>;
using viii = vector<piii>;
using vvi = vector<vi>;
using vvii = vector<vii>;
using vviii = vector<viii>;
template <class T>
using min_queue = priority_queue<T, vector<T>, greater<T> >;
template <class T>
using max_queue = priority_queue<T>;
template <size_t... I>
struct my_index_sequence {
  using type = my_index_sequence;
  static constexpr array<size_t, sizeof...(I)> value = {{I...}};
};
namespace my_index_sequence_detail {
template <typename I, typename J>
struct concat;
template <size_t... I, size_t... J>
struct concat<my_index_sequence<I...>, my_index_sequence<J...> >
    : my_index_sequence<I..., (sizeof...(I) + J)...> {};
template <size_t N>
struct make_index_sequence
    : concat<typename make_index_sequence<N / 2>::type,
             typename make_index_sequence<N - N / 2>::type>::type {};
template <>
struct make_index_sequence<0> : my_index_sequence<> {};
template <>
struct make_index_sequence<1> : my_index_sequence<0> {};
}  // namespace my_index_sequence_detail
template <class... A>
using my_index_sequence_for =
    typename my_index_sequence_detail::make_index_sequence<sizeof...(A)>::type;
template <class T, size_t... I>
void print_tuple(ostream& s, T const& a, my_index_sequence<I...>) {
  using swallow = int[];
  (void)swallow{0, (void(s << (I == 0 ? "" : ", ") << get<I>(a)), 0)...};
}
template <class T>
ostream& print_collection(ostream& s, T const& a);
template <class... A>
ostream& operator<<(ostream& s, tpl<A...> const& a);
template <class... A>
ostream& operator<<(ostream& s, tuple<A...> const& a);
template <class A, class B>
ostream& operator<<(ostream& s, pair<A, B> const& a);
template <class T, size_t I>
ostream& operator<<(ostream& s, array<T, I> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& operator<<(ostream& s, vector<T> const& a) {
  return print_collection(s, a);
}
template <class T, class U>
ostream& operator<<(ostream& s, multimap<T, U> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& operator<<(ostream& s, multiset<T> const& a) {
  return print_collection(s, a);
}
template <class T, class U>
ostream& operator<<(ostream& s, map<T, U> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& operator<<(ostream& s, set<T> const& a) {
  return print_collection(s, a);
}
template <class T>
ostream& print_collection(ostream& s, T const& a) {
  s << '[';
  for (auto it = begin(a); it != end(a); ++it) {
    s << *it;
    if (it != prev(end(a))) s << " ";
  }
  return s << ']';
}
template <class... A>
ostream& operator<<(ostream& s, tpl<A...> const& a) {
  s << '(';
  print_tuple(s, a, my_index_sequence_for<A...>{});
  return s << ')';
}
template <class... A>
ostream& operator<<(ostream& s, tuple<A...> const& a) {
  s << '(';
  print_tuple(s, a, my_index_sequence_for<A...>{});
  return s << ')';
}
template <class A, class B>
ostream& operator<<(ostream& s, pair<A, B> const& a) {
  return s << "(" << get<0>(a) << ", " << get<1>(a) << ")";
}
const int BSIZE = 300;
struct SuffixAutomaton {
  int edges[26][1 + BSIZE * 2], link[1 + BSIZE * 2], length[1 + BSIZE * 2],
      isTerminal[1 + BSIZE * 2], dp1[1 + BSIZE * 2], last;
  int sz;
  SuffixAutomaton() {
    last = 0;
    sz = 0;
  }
  void set(int k) {
    for (int i = 0; i < 26; ++i) edges[i][k] = -1;
  }
  void build(char* s, int size) {
    link[0] = -1;
    length[0] = 0;
    last = 0;
    sz = 1;
    set(0);
    for (int i = 0; i < size; i++) {
      set(sz);
      length[sz] = i + 1;
      link[sz] = 0;
      int r = sz;
      ++sz;
      int p = last;
      while (p >= 0 && edges[s[i] - 'a'][p] == -1) {
        edges[s[i] - 'a'][p] = r;
        p = link[p];
      }
      if (p != -1) {
        int q = edges[s[i] - 'a'][p];
        if (length[p] + 1 == length[q]) {
          link[r] = q;
        } else {
          for (int i = 0; i < 26; ++i) {
            edges[i][sz] = edges[i][q];
          }
          length[sz] = length[p] + 1;
          link[sz] = link[q];
          int qq = sz;
          ++sz;
          link[q] = qq;
          link[r] = qq;
          while (p >= 0 && edges[s[i] - 'a'][p] == q) {
            edges[s[i] - 'a'][p] = qq;
            p = link[p];
          }
        }
      }
      last = r;
    }
    for (int i = 0; i < sz; ++i) isTerminal[i] = 0, dp1[i] = -1;
    int p = last;
    while (p > 0) {
      isTerminal[p] = 1;
      p = link[p];
    }
  }
  int solve(int pos) {
    if (dp1[pos] != -1) return dp1[pos];
    dp1[pos] = isTerminal[pos];
    for (int i = 0; i < 26; ++i) {
      if (edges[i][pos] != -1) dp1[pos] += solve(edges[i][pos]);
    }
    return dp1[pos];
  }
  int run(char const* sq) {
    int cur = 0;
    for (int i = 0; sq[i] != '\0'; ++i) {
      auto it = edges[sq[i] - 'a'][cur];
      if (it == -1)
        return 0;
      else
        cur = it;
    }
    return solve(cur);
  }
};
vi kmp_build(string const& s) {
  int n = s.size();
  vi T(n + 1);
  T[0] = -1;
  for (lli i = 0; i < (lli)(n); ++i) {
    int b = T[i];
    while (b != -1 && s[i] != s[b]) b = T[b];
    T[i + 1] = b + 1;
  }
  return T;
}
int kmp_next(string const& s, vi const& T, int i, int x) {
  while (i != -1 && x != s[i]) i = T[i];
  return i + 1;
}
SuffixAutomaton B[100000 / BSIZE + 10];
int clean[100000 / BSIZE + 10];
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  string s;
  cin >> s;
  int n = s.size();
  int nblock = (n + BSIZE - 1) / BSIZE;
  int q;
  cin >> q;
  for (lli q_ = 0; q_ < (lli)(q); ++q_) {
    int ty;
    cin >> ty;
    if (ty == 1) {
      int i;
      char c;
      cin >> i >> c;
      --i;
      if (s[i] == c) continue;
      s[i] = c;
      clean[i / BSIZE] = 0;
    } else {
      lli l, r;
      string y;
      cin >> l >> r >> y;
      --l;
      --r;
      lli ans = 0;
      if (y.size() > 150) {
        auto T = kmp_build(y);
        lli S = 0;
        for (lli i = (l); i <= (lli)(r); ++i) {
          S = kmp_next(y, T, S, s[i]);
          if (S == (int)y.size()) ans += 1;
        }
      } else {
        lli bl = l / BSIZE;
        lli br = r / BSIZE;
        auto T = kmp_build(y);
        {
          lli S = 0;
          for (lli i = (l); i <= (lli)(min(r, (bl + 1) * BSIZE - 1)); ++i) {
            S = kmp_next(y, T, S, s[i]);
            if (S == (int)y.size()) ans += 1;
          }
        }
        if (bl != br) {
          lli S = 0;
          for (lli i = (br * BSIZE); i <= (lli)(r); ++i) {
            S = kmp_next(y, T, S, s[i]);
            if (S == (int)y.size()) ans += 1;
          }
        }
        for (lli b = (bl + 1); b <= (lli)(br - 1); ++b) {
          if (!clean[b]) {
            clean[b] = 1;
            B[b].build(&s[b * BSIZE], min<int>(BSIZE, s.size() - b * BSIZE));
          }
          ans += B[b].run(y.c_str());
        }
        for (lli b = (bl); b <= (lli)(br - 1); ++b) {
          int S = 0;
          int from = max<int>(l, (b + 1) * BSIZE - y.size() + 1);
          int to = min<int>(r, (b + 1) * BSIZE + y.size() - 2);
          for (lli i = (from); i <= (lli)(to); ++i) {
            S = kmp_next(y, T, S, s[i]);
            if (S == (int)y.size()) ans += 1;
          }
        }
      }
      cout << ans << '\n';
    }
  }
  return 0;
}