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.io.*;
import java.math.BigInteger;
import java.util.*;
import java.util.Map.Entry;

	
public class Main
	{
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;
		private PrintWriter pw;
		private long mod = 1000000000 + 7;
		
		private StringBuilder ans_sb;
		private int block;
		private double ans = 0;
		private void soln()
		{
			char[] s = nextLine().toCharArray();
			int n = s.length;
			BitSet[] set = new BitSet[26];
			BitSet allset = new BitSet();
			allset.set(0, n, true);
			for(int i=0;i<26;i++)
				set[i] = new BitSet();
			for(int i=0;i<n;i++) 
				set[s[i]-'a'].set(n-i-1);
		//	debug(set[0].get(0,n-1));
			int q = nextInt();
			while(q-- > 0) {
				String[] tmp = nextLine().split(" ");
				int t = Integer.parseInt(tmp[0]);
				if(t == 1) {
					int i = Integer.parseInt(tmp[1]) - 1;
					char c = tmp[2].charAt(0);
					set[s[i]-'a'].clear(n-i-1);
					set[c-'a'].set(n-i-1);
					s[i] = c;
				}else {
					int l = n - Integer.parseInt(tmp[1]);
					int r = n - Integer.parseInt(tmp[2]);
					String y = tmp[3];
					if(l - r + 1 < y.length()) {
						pw.println(0);
						continue;
					}
					BitSet aset = new BitSet();
					aset.or(allset);
					for(int i = 0; i<y.length();i++) {
						aset.and(set[y.charAt(i)-'a']);
						if(i != y.length() - 1)
							aset = aset.get(1, n);
					}
					
					int ans = aset.get(r, l-y.length()+2).cardinality();
					pw.println(ans);
				}
			}
		}
		private class Pair implements Comparable<Pair>{
			long s,h,ans;
			public Pair(long a,long b,long c) {
				s = a;
				h = b;
				ans = c;
			}
			@Override
			public int compareTo(Pair arg0)
			{
				long mul1 = this.s * arg0.h;
				long mul2 = this.h * arg0.s;
			//	if(mul1 != mul2)
				if(mul1>mul2)
					return -1;
				else if(mul2 > mul1)
					return 1;
				return 0;
				
			//	return 0;
			}
		}
		private String solveEqn(long a, long b) {
	        long x = 0, y = 1, lastx = 1, lasty = 0, temp;
	        while (b != 0){
	        	long q = a / b;
	        	long r = a % b;
	            a = b;
	            b = r;
	            temp = x;
	            x = lastx - q * x;
	            lastx = temp;
	            temp = y;
	            y = lasty - q * y;
	            lasty = temp;
	        }
	        return lastx+" "+lasty;
		}
		private void debug(Object... o) {
			System.out.println(Arrays.deepToString(o));
		}
		
		private long pow(long a, long b, long c)
		{
			if (b == 0)
				return 1;
			long p = pow(a, b / 2, c);
			p = (p * p) % c;
			return (b % 2 == 0) ? p : (a * p) % c;
		}
	
		private long gcd(long n, long l)
		{
			if (l == 0)
				return n;
			return gcd(l, n % l);
		}
		public static void main(String[] args) throws Exception
		{
			new Thread(null, new Runnable()
			{
				@Override
				public void run()
				{
					new Main().solve();
				}
			}, "1", 1 << 25).start();
		//	new Main().solve();
		}
		public StringBuilder solve(){
			InputReader(System.in);
			/*try { 
				InputReader(new FileInputStream("C:\\Users\\hardik\\Desktop\\in.txt"));
			} catch(FileNotFoundException e) {}
			*/
			pw = new PrintWriter(System.out);
			//ans_sb = new StringBuilder();
			soln();
			
			pw.close();
			//System.out.println(ans_sb);
			return ans_sb;
		}
		public void InputReader(InputStream stream1)
		{
			stream = stream1;
		}
	
		private boolean isWhitespace(int c)
		{
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	
		private boolean isEndOfLine(int c)
		{
			return c == '\n' || c == '\r' || c == -1;
		}
	
		private int read()
		{
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars)
			{
				curChar = 0;
				try
				{
					numChars = stream.read(buf);
				} catch (IOException e)
				{
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
	
		private int nextInt()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = read();
			}
			int res = 0;
			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
	
		private long nextLong()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = read();
			}
			long res = 0;
			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
	
		private String nextToken()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do
			{
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}
	
		private String nextLine()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do
			{
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}
	
		private int[] nextIntArray(int n)
		{
			int[] arr = new int[n];
			for (int i = 0; i < n; i++)
			{
				arr[i] = nextInt();
			}
			return arr;
		}
	
		private long[] nextLongArray(int n)
		{
			long[] arr = new long[n];
			for (int i = 0; i < n; i++)
			{
				arr[i] = nextLong();
			}
			return arr;
		}
	
		private void pArray(int[] arr)
		{
			for (int i = 0; i < arr.length; i++)
			{
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			return;
		}
	
		private void pArray(long[] arr)
		{
			for (int i = 0; i < arr.length; i++)
			{
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			return;
		}
	
		private boolean isSpaceChar(int c)
		{
			if (filter != null)
				return filter.isSpaceChar(c);
			return isWhitespace(c);
		}
	
		private char nextChar()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			char c1 = (char) c;
			while (!isSpaceChar(c))
				c = read();
			return c1;
		}
	
		private interface SpaceCharFilter
		{
			public boolean isSpaceChar(int ch);
		}
	}