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 JAVA):

Solution:
import java.util.*;
import java.math.*;
import java.io.*;

public class CF914F {
	class SuffixAutomaton {
		final int ALPHA = 26;
		final int OFFSET = 'a';
		int next, MAX, last, dp[], len[], link[], trie[][];
		boolean[] terminal;
		public SuffixAutomaton(int n) {
			// max number of states is 2n - 1
			MAX = n << 1;
			dp = new int[MAX];
			len = new int[MAX];
			link = new int[MAX];
			trie = new int[ALPHA][MAX];
			terminal = new boolean[MAX];
		}
		void reset() {
			Arrays.fill(dp, 0);
			Arrays.fill(len, 0);
			Arrays.fill(link, 0);
			Arrays.fill(terminal, false);
			for(int let = 0 ; let < 26 ; let++)
				Arrays.fill(trie[let], 0);
		}
		void build(char[] s, int l, int r) {
			next = 1;  last = 0;
			link[0] = -1;
			for(int i = l ; i <= r ; i++) {
				int c = s[i] - OFFSET;
				int cur = next++;
				len[cur] = len[last] + 1;
				int p = last;
				while(p != -1 && trie[c][p] == 0) {
					trie[c][p] = cur;
					p = link[p];
				}
				if(p == -1) {
					link[cur] = 0;
				} else {
					int q = trie[c][p];
					if(len[p] + 1 == len[q]) {
						link[cur] = q;
					} else {
						int clone = next++;
						len[clone] = len[p] + 1;
						link[clone] = link[q];
						for(int let = 0 ; let < ALPHA ; let++)
							trie[let][clone] = trie[let][q];
						while(p != -1 && trie[c][p] == q) {
							trie[c][p] = clone;
							p = link[p];
						}
						link[q] = link[cur] = clone;
					}
				}
				last = cur;
			}
			int p = last;
			while(p > 0) {
				terminal[p] = true;
				p = link[p];
			}
		}
		int count(char[] t) {
			int node = 0;
			for(char c : t) {
				int let = c - OFFSET;
				if(trie[let][node] == 0) return 0;
				node = trie[let][node];
			}
			return go(node);
		}
		int go(int node) {
			if(dp[node] != 0) return dp[node];
			if(terminal[node]) dp[node]++;
			for(int i = 0 ; i < ALPHA ; i++) {
				if(trie[i][node] != 0) {
					go(trie[i][node]);
					dp[node] += dp[trie[i][node]];
				}
			}
			return dp[node];
		}
	}
	char[] Z;
	int bruteforce(char[] s, char[] t, int l, int r) {
		for(int i = 0 ; i < t.length ; i++)
			Z[i] = t[i];
		for(int i = l ; i <= r ; i++)
			Z[i - l + t.length] = s[i];
		int n = r - l + 1 + t.length, L = 0, R = 0;
		int[] z = new int[n];
		z[0] = n;
		for(int i = 1 ; i < n ; i++) {
			if(i > R) {
				L = R = i;
				while(R < n && Z[R - L] == Z[R]) R++;
				z[i] = R - L;
				R--;
			} else {
				int k = i - L;
				if(z[k] < R - i + 1) {
					z[i] = z[k];
				} else {
					L = i;
					while(R < n && Z[R - L] == Z[R]) R++;
					z[i] = R - L;
					R--;
				}
			}
		}
		int res = 0;
		for(int i = t.length ; i < n ; i++)
			if(z[i] >= t.length)
				res++;
		return res;
	}
	int n, root;
	public CF914F() {
		FS scan = new FS();
		PrintWriter out = new PrintWriter(System.out);
		char[] s = scan.next().toCharArray();
		n = s.length;
		root = ((int) Math.sqrt(n));
		if(root * root < n) root++;
		SuffixAutomaton[] sa = new SuffixAutomaton[root];
		int[][] range = new int[2][(n + root - 1) / root];
		for(int i = 0 ; i < (n + root - 1) / root ; i++) {
			range[0][i] = i * root;
			range[1][i] = Math.min(n - 1, ((i + 1) * root) - 1);
			sa[i] = new SuffixAutomaton(root);
			sa[i].build(s, range[0][i], range[1][i]);
		}
		Z = new char[200200];
		int q = scan.nextInt();
		for(int qq = 0 ; qq < q ; qq++) {
			int type = scan.nextInt();
			if(type == 1) {
				int i = scan.nextInt() - 1;
				char c = scan.next().charAt(0);
				int bucket = i / root;
				s[i] = c;
				sa[bucket].reset();
				sa[bucket].build(s, range[0][bucket], range[1][bucket]);
			} else {
				int l = scan.nextInt() - 1, r = scan.nextInt() - 1;
				char[] t = scan.next().toCharArray();
				int res = 0;
				if(t.length >= root || r - l <= 2 * root) {
					res = bruteforce(s, t, l, r);
				} else {
					int lbucket = l / root, rbucket = r / root;
					for(int i = lbucket + 1 ; i < rbucket ; i++)
						res += sa[i].count(t);
					res += bruteforce(s, t, l, (lbucket + 1) * root - 1);
					res += bruteforce(s, t, rbucket * root, r);
					for(int i = lbucket + 1 ; i <= rbucket ; i++)
						res += bruteforce(s, t, Math.max(l, range[0][i] - t.length + 1), Math.min(r, range[0][i] + t.length - 2));
				}
				out.println(res);
			}
		}
		out.close();
	}
	class FS {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");
		public String next() {
			while(!st.hasMoreTokens()) {
				try { st = new StringTokenizer(br.readLine()); }
				catch(Exception e) { e.printStackTrace(); }
			}
			return st.nextToken();
		}
		public int nextInt() { return Integer.parseInt(next()); }
	}
	public static void main(String[] args) { new CF914F(); }
}