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 javax.print.DocFlavor;
import javax.swing.text.html.HTMLDocument;
import javax.xml.stream.util.EventReaderDelegate;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.security.KeyPair;
import java.util.*;

public class Main {

    static long[][] c ;
    static int[][] arr;
    static int dp[][];
    static long[] parent; /// DSU
    static boolean[][] ans;
    static int n , m;
    static int MAXN =(int) 1e6 + 10;
    static int[][] BIT = new int[MAXN][26];
    static int k = (int)(Math.ceil(Math.log(n)/Math.log(2)));

    public static void main(String[] args) throws IOException {
        Reader.init(System.in);
        String s = Reader.next();
        char[] arr = s.toCharArray();
        int q = Reader.nextInt();
        n = arr.length;
        for (int i = 0 ; i < arr.length ; i++){
            update(i+1 , 1,arr[i]);
        }
        //System.out.println(query(arr.length,0));
        while (q-->0){
            int n1 = Reader.nextInt();
            if (n1==1){
                int pos = Reader.nextInt();
                String x = Reader.next();
                char c = x.charAt(0);
                update(pos,-1,arr[pos-1]);
                update(pos,1,c);
                arr[pos-1] = c;
            }
            else{
                int ans = 0;
                int l = Reader.nextInt();
                int r = Reader.nextInt();
                for (int i = 0 ; i < 26 ; i++){
                    int l1 = query(l-1,i);
                    int r1 = query(r,i);
                    //System.out.println(r1 + " " + l1);
                    if (r1>l1){
                        ans++;
                    }
                }
                System.out.println(ans);
            }
        }


    }

    static void update(int x , int val,char a){

        while (x<=n){
            BIT[x][a-'a']+=val;
            x+=(x&-x);
        }
    }

    static int query(int x,int a){
        int res= 0;
        while (x>0){
            res+=BIT[x][a];
            x-=(x&-x);
        }
        return res;
    }



    static long power(long x, long y, long p)
    {
        // Initialize result
        long res = 1;

        // Update x if it is more
        // than or equal to p
        x = x % p;

        while (y > 0)
        {
            // If y is odd, multiply x
            // with result
            if((y & 1)==1)
                res = (res * x) % p;

            // y must be even now
            // y = y / 2
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }



    static boolean fun(int n){
        int[] cnt = new int[10];
        String x = Integer.toString(n);
        for (int i = 0 ; i < x.length() ; i++){
            cnt[x.charAt(i)-'0']++;
        }
        for (int i = 0 ; i < 10 ; i++){
            if (cnt[i]>1){
                return false;
            }
        }
        return true;
    }

    static int rec(int row ,int col, int mask){
        //System.out.println(row + " " + col + " " + mask);
        if (row==n-1){
            if (mask!=0){
                ans[row][col] = true;
                return 1;
            }
            return 0;
        }
        if (dp[row][mask]!=-1){
            return dp[row][mask];
        }

        for (int i = 0 ;i < m ; i++){
            if (rec(row+1,i,mask^arr[row+1][i])==1){
                ans[row][col] = true;
                return dp[row][mask] = 1;
            }
        }
        return dp[row][mask]= 0;


    }

    static class Node implements Comparable<Node>{
        int a;
        int b;
        Node(int a , int b){
            this.a  = a;
            this.b  = b;
        }

        @Override
        public int compareTo(Node o) {
            if (this.a != o.a ){
                return this.a - o.a;
            }
            else{
                return this.b - this.b;
            }
        }
    }



    static long find(int a){
        if (parent[a]!=a){
            parent[a] = find((int)parent[a]);
        }
        return parent[a];
    }




    public static void sortbyColumn_asc(int arr[][], int col)
    {
        // Using built-in sort function Arrays.sort
        Arrays.sort(arr, new Comparator<int[]>() {

            @Override
            // Compare values according to columns
            public int compare(final int[] entry1,
                               final int[] entry2) {

                // To sort in descending order revert
                // the '>' Operator
                if (entry1[col] > entry2[col])
                    return 1;
                else
                    return -1;
            }
        });  // End of function call sort().
    }

    public static void sortbyColumn_dsc(int arr[][], int col)
    {
        // Using built-in sort function Arrays.sort
        Arrays.sort(arr, new Comparator<int[]>() {

            @Override
            // Compare values according to columns
            public int compare(final int[] entry1,
                               final int[] entry2) {

                // To sort in descending order revert
                // the '>' Operator
                if (entry1[col] > entry2[col])
                    return -1;
                else
                    return 1;
            }
        });  // End of function call sort().
    }

    static void swap(char[] arr , int i , int j){
        char tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    static void swap(int[] arr , int i , int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }





}

class Node implements Comparable<Node>{
    int a ;
    int b;
    Node(int a , int b){
        this.a = a;
        this.b = b;
    }
    public int compareTo(Node o) {
        if (this.a < o.a && this.b < o.b){
            return -1;
        }
        else{
            return 1;
        }
    }
}
class Edge implements Comparable<Edge>{
    int x , y , w;

    public Edge(int x, int y, int w) {
        this.x = x;
        this.y = y;
        this.w = w;
    }

    @Override
    public int compareTo(Edge o) {
        return this.w - o.w;
    }
}
class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
        reader = new BufferedReader(
                new InputStreamReader(input) );
        tokenizer = new StringTokenizer("");
    }
    /** get next word */
    static String next() throws IOException {
        while ( ! tokenizer.hasMoreTokens() ) {
            //TODO add check for eof if necessary
            tokenizer = new StringTokenizer(
                    reader.readLine() );
        }
        return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
        return Integer.parseInt( next() );
    }
    static long nextLong() throws IOException {
        return Long.parseLong( next() );
    }

    static double nextDouble() throws IOException {
        return Double.parseDouble( next() );
    }
}
class MergeSort
{
    // Merges two subarrays of arr[].
    // First subarray is arr[l..m]
    // Second subarray is arr[m+1..r]
    void merge(int arr[], int l, int m, int r)
    {
        // Find sizes of two subarrays to be merged
        int n1 = m - l + 1;
        int n2 = r - m;

        /* Create temp arrays */
        int L[] = new int [n1];
        int R[] = new int [n2];

        /*Copy data to temp arrays*/
        for (int i=0; i<n1; ++i)
            L[i] = arr[l + i];
        for (int j=0; j<n2; ++j)
            R[j] = arr[m + 1+ j];


        /* Merge the temp arrays */

        // Initial indexes of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarry array
        int k = l;
        while (i < n1 && j < n2)
        {
            if (L[i] <= R[j])
            {
                arr[k] = L[i];
                i++;
            }
            else
            {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        /* Copy remaining elements of L[] if any */
        while (i < n1)
        {
            arr[k] = L[i];
            i++;
            k++;
        }

        /* Copy remaining elements of R[] if any */
        while (j < n2)
        {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    // Main function that sorts arr[l..r] using
    // merge()
    void sort(int arr[], int l, int r)
    {
        if (l < r)
        {
            // Find the middle point
            int m = (l+r)/2;

            // Sort first and second halves
            sort(arr, l, m);
            sort(arr , m+1, r);

            // Merge the sorted halves
            merge(arr, l, m, r);
        }
    }

    /* A utility function to print array of size n */
    static void printArray(int arr[])
    {
        int n = arr.length;
        for (int i=0; i<n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    // Driver method

}