You are given a string s consisting of lowercase Latin letters and q queries for this string.

Recall that the substring s[l; r] of the string s is the string s_l s_{l + 1} ... s_r. For example, the substrings of "codeforces" are "code", "force", "f", "for", but not "coder" and "top".

There are two types of queries: 

  * 1~ pos~ c (1 ≤ pos ≤ |s|, c is lowercase Latin letter): replace s_{pos} with c (set s_{pos} := c); 
  * 2~ l~ r (1 ≤ l ≤ r ≤ |s|): calculate the number of distinct characters in the substring s[l; r]. 

Input

The first line of the input contains one string s consisting of no more than 10^5 lowercase Latin letters.

The second line of the input contains one integer q (1 ≤ q ≤ 10^5) — the number of queries.

The next q lines contain queries, one per line. Each query is given in the format described in the problem statement. It is guaranteed that there is at least one query of the second type.

Output

For each query of the second type print the answer for it — the number of distinct characters in the required substring in this query.

Examples

Input


abacaba
5
2 1 4
1 4 b
1 5 b
2 4 6
2 1 7


Output


3
1
2


Input


dfcbbcfeeedbaea
15
1 6 e
1 4 b
2 6 14
1 7 b
1 12 c
2 6 8
2 1 6
1 7 c
1 2 f
1 10 a
2 7 9
1 10 a
1 14 b
1 1 f
2 1 11


Output


5
2
5
2
6


import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class D {

	public static class SegmentTree  
	{ 
	    int st[]; // The array that stores segment tree nodes 
	  
	    /* Constructor to construct segment tree from given array. This 
	       constructor  allocates memory for segment tree and calls 
	       constructSTUtil() to  fill the allocated memory */
	    SegmentTree(int arr[], int n) 
	    { 
	        // Allocate memory for segment tree 
	        //Height of segment tree 
	        int x = (int) (Math.ceil(Math.log(n) / Math.log(2))); 
	  
	        //Maximum size of segment tree 
	        int max_size = 2 * (int) Math.pow(2, x) - 1; 
	  
	        st = new int[max_size]; // Memory allocation 
	  
	        constructSTUtil(arr, 0, n - 1, 0); 
	    } 
	  
	    // A utility function to get the middle index from corner indexes. 
	    int getMid(int s, int e) { 
	        return s + (e - s) / 2; 
	    } 
	  
	    /*  A recursive function to get the sum of values in given range 
	        of the array.  The following are parameters for this function. 
	  
	      st    --> Pointer to segment tree 
	      si    --> Index of current node in the segment tree. Initially 
	                0 is passed as root is always at index 0 
	      ss & se  --> Starting and ending indexes of the segment represented 
	                    by current node, i.e., st[si] 
	      qs & qe  --> Starting and ending indexes of query range */
	    int getSumUtil(int ss, int se, int qs, int qe, int si) 
	    { 
	        // If segment of this node is a part of given range, then return 
	        // the sum of the segment 
	        if (qs <= ss && qe >= se) 
	            return st[si]; 
	  
	        // If segment of this node is outside the given range 
	        if (se < qs || ss > qe) 
	            return 0; 
	  
	        // If a part of this segment overlaps with the given range 
	        int mid = getMid(ss, se); 
	        return getSumUtil(ss, mid, qs, qe, 2 * si + 1) + 
	                getSumUtil(mid + 1, se, qs, qe, 2 * si + 2); 
	    } 
	  
	    /* A recursive function to update the nodes which have the given  
	       index in their range. The following are parameters 
	        st, si, ss and se are same as getSumUtil() 
	        i    --> index of the element to be updated. This index is in 
	                 input array. 
	       diff --> Value to be added to all nodes which have i in range */
	    void updateValueUtil(int ss, int se, int i, int diff, int si) 
	    { 
	        // Base Case: If the input index lies outside the range of  
	        // this segment 
	        if (i < ss || i > se) 
	            return; 
	  
	        // If the input index is in range of this node, then update the 
	        // value of the node and its children 
	        st[si] = st[si] + diff; 
	        if (se != ss) { 
	            int mid = getMid(ss, se); 
	            updateValueUtil(ss, mid, i, diff, 2 * si + 1); 
	            updateValueUtil(mid + 1, se, i, diff, 2 * si + 2); 
	        } 
	    } 
	  
	    // The function to update a value in input array and segment tree. 
	   // It uses updateValueUtil() to update the value in segment tree 
	    void updateValue(int arr[], int n, int i, int new_val) 
	    { 
	        // Check for erroneous input index 
	        if (i < 0 || i > n - 1) { 
	            System.out.println("Invalid Input"); 
	            return; 
	        } 
	  
	        // Get the difference between new value and old value 
	        int diff = new_val - arr[i]; 
	  
	        // Update the value in array 
	        arr[i] = new_val; 
	  
	        // Update the values of nodes in segment tree 
	        updateValueUtil(0, n - 1, i, diff, 0); 
	    } 
	  
	    // Return sum of elements in range from index qs (quey start) to 
	   // qe (query end).  It mainly uses getSumUtil() 
	    int getSum(int n, int qs, int qe) 
	    { 
	        // Check for erroneous input values 
	        if (qs < 0 || qe > n - 1 || qs > qe) { 
	            System.out.println("Invalid Input"); 
	            return -1; 
	        } 
	        return getSumUtil(0, n - 1, qs, qe, 0); 
	    } 
	  
	    // A recursive function that constructs Segment Tree for array[ss..se]. 
	    // si is index of current node in segment tree st 
	    int constructSTUtil(int arr[], int ss, int se, int si) 
	    { 
	        // If there is one element in array, store it in current node of 
	        // segment tree and return 
	        if (ss == se) { 
	            st[si] = arr[ss]; 
	            return arr[ss]; 
	        } 
	  
	        // If there are more than one elements, then recur for left and 
	        // right subtrees and store the sum of values in this node 
	        int mid = getMid(ss, se); 
	        st[si] = constructSTUtil(arr, ss, mid, si * 2 + 1) + 
	                 constructSTUtil(arr, mid + 1, se, si * 2 + 2); 
	        return st[si]; 
	    } 

	}

	public static int[] readInts(String cad) {
		String read[] = cad.split(" ");
		int res[] = new int[read.length];
		for (int i = 0; i < read.length; i++) {
			res[i] = Integer.parseInt(read[i]);
		}
		return res;
	}
	public static void main(String[] args) throws IOException {
		StringBuilder out = new StringBuilder();
		BufferedReader in;
		
			in = new BufferedReader(new InputStreamReader(System.in));
	
		char array[] = in.readLine().toCharArray();
		int q = Integer.parseInt(in.readLine());
		
		SegmentTree trees[] = new SegmentTree[26];
		int arrays[][] = new int[26][];
		int total[] = new int[26];
		for( int i = 0 ; i< 26; i++ ) {
			arrays[i] = new int[array.length];
			
			for(int j = 0; j < array.length; j++ ) {
				if( array[j] - 'a' == i)
					arrays[i][j] = 1;
				if( i == 0 )
					total[array[j] - 'a']++;
			}
			trees[i] = new SegmentTree(arrays[i], array.length);		
		}
			
		
		
		for( int i = 0; i < q; i++ ) {
			String values[] = in.readLine().split(" ");
			
			int type = Integer.parseInt(values[0]);
			
			if(type == 1) {
				int id = Integer.parseInt(values[1]);
				int letter = values[2].charAt(0) - 'a';
				
				int lastLetter = array[id-1] - 'a';
				
				total[letter]++;
				total[lastLetter]--;
				trees[lastLetter].updateValue(arrays[lastLetter], arrays[lastLetter].length, id-1, 0);
				trees[letter].updateValue(arrays[letter], arrays[letter].length, id-1, 1);
				
				array[id-1] = values[2].charAt(0);
				
			}else {
				int l = Integer.parseInt(values[1]);
				int r = Integer.parseInt(values[2]);
				int res = 0;
				for( int k =0; k < 26; k++ ) {
					if( total[k] > 0 ) {
						int sum = trees[k].getSum(array.length, l-1, r-1);
						if( sum > 0)
							res++;
					}
					
				}
				
				out.append(res + "\n");
			}
		}
		System.out.print(out);
	}
}
