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.util.*;
import java.io.*;
  
public class A2 {   
 
    public static BufferedReader br;
    public static StringTokenizer st;
    public static String next() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                throw new RuntimeException(e);
            }
        }
        return st.nextToken();
    }
 
    public static Integer nextInt() {
        return Integer.parseInt(next());
    }
 
    public static Long nextLong() {
        return Long.parseLong(next());
    }
 
    public static Double nextDouble() {
        return Double.parseDouble(next());
    }
 
    static long fast_pow(long base,long n,long M)
    {
        if(n==0)
           return 1;
        if(n==1)
        return base;
        long halfn=fast_pow(base,n/2,M);
        if(n%2==0)
            return ( halfn * halfn ) % M;
        else
            return ( ( ( halfn * halfn ) % M ) * base ) % M;
    }
 
    static long finextDoubleMMI_fermat(long n,int M)
    {
        return fast_pow(n,M-2,M);
    }
 
    static long nCrModPFermat(int n, int r, int p) 
    { 
        if (r == 0) 
            return 1; 
        long[] fac = new long[n+1]; 
        fac[0] = 1;           
        for (int i = 1 ;i <= n; i++) 
            fac[i] = fac[i-1] * i % p;       
        return (fac[n]* finextDoubleMMI_fermat(fac[r], p)% p * finextDoubleMMI_fermat(fac[n-r], p) % p) % p; 
    } 
 
    static void merge(int arr[], int l, int m, int r) 
    { 
        int n1 = m - l + 1; 
        int n2 = r - m; 
  
        int L[] = new int [n1]; 
        int R[] = new int [n2]; 
  
        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]; 
        int i = 0, j = 0; 
        
        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++; 
        } 
  
        while (i < n1) 
        { 
            arr[k] = L[i]; 
            i++; 
            k++; 
        } 
  
        while (j < n2) 
        { 
            arr[k] = R[j]; 
            j++; 
            k++; 
        } 
    } 
  
    static void sort(int arr[], int l, int r) 
    { 
        if (l < r) 
        { 
            int m = (l+r)/2; 
            sort(arr, l, m); 
            sort(arr , m+1, r); 
            merge(arr, l, m, r); 
        } 
    } 
 
    static void sort(int arr[]) 
    { 
        int l=0;
        int r=arr.length-1;
        if (l < r) 
        { 
            int m = (l+r)/2; 
            sort(arr, l, m); 
            sort(arr , m+1, r); 
            merge(arr, l, m, r); 
        } 
    } 

    static long gcd(long a, long b){
        if(a%b==0)
            return b;
        if(b%a==0)
            return a;
        if(a>b)
            return gcd(a%b,b);
        return gcd(a,b%a);
    }

    static class Item{
        int a;
        int b;
        Item(int a,int b){
            this.a=a;
            this.b=b;
        }
    }
 
    static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    
    static class sorting implements Comparator<Item>{  
        public int compare(Item o1,Item o2){  
            if(o1.a==o2.a)
                return (o1.b>o2.b)?1:-1;  
            else if(o1.a>o2.a)  
                return 1;  
            else  
                return -1;  
        }
    }  
    static int h[];
    static void RMQUtil(int ss, int se, int qs, int qe, int index) 
    { 
        // If segment of this node is a part of given range, then 
        // return the min of the segment 
        if(index<0||index>=y)
            return;
        if (qs <= ss && qe >= se) {
            // ArrayList<Integer> ar=new ArrayList<>();
            for(int i=0;i<26;i++){
                h[i]+=st2[index][i];
            }
            return;
            // return st2[index]; 
        }
        if(ss>qe||se<qs)
            return;
        RMQUtil(ss, (ss+se)/2, qs, qe, 2 * index + 1);
        RMQUtil((ss+se)/2 + 1, se, qs, qe, 2 * index + 2);
    } 
  
    // Return minimum of elements in range from index qs (quey 
    // start) to qe (query end).  It mainly uses RMQUtil() 
    static int record(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; 
        } 
        h=new int[26];
        // for()
        RMQUtil(0, n - 1, qs, qe, 0);
        // for(int i=0;i<26;i++)
        //     pw.print(h[i]+" ");
        // pw.println();
        int c=0;
        for(int i=0;i<26;i++)
        {

            if(h[i]>0){
                // pw.print(h[i]+" "+c+" ");
                c++;
            }
        } 
        return c;
    } 
  
    // A recursive function that constructs Segment Tree for 
    // array[ss..se]. si is index of current node in segment tree st 
    static void constructSTUtil(int arr[], int ss, int se, int si) 
    { 
        if (ss == se) { 
            st2[si][arr[ss]]++; 
            return;
        } 
        int mid=(se+ss)/2;
        constructSTUtil(arr, ss, mid, si * 2 + 1);
        constructSTUtil(arr, mid + 1, se, si * 2 + 2);
        for(int i=0;i<26;i++){
            if(si*2+1<st2.length)
                st2[si][i]+=st2[si*2+1][i];
            if(si*2+2<st2.length)
                st2[si][i]+=st2[si*2+2][i];
        }
    } 
  
    static int st2[][];
    static int y=0;
    static void constructST(int arr[], int n) 
    { 
        int x = (int) (Math.ceil(Math.log(n) / Math.log(2))); 
        int max_size = y = 2 * (int) Math.pow(2, x) - 1; 
        st2 = new int[max_size][26]; 
        constructSTUtil(arr, 0, n - 1, 0); 
    }

    static void update(int pos,int i,int j,int p,int q,int si){
        // pw.println(si);
        if(si>=y)
            return;
        if(i<=pos&&pos<=j){
            // pw.println(si);
            st2[si][p]++;
            // st2[si][p]++;
            st2[si][q]--;
            // st2[si][q]--;
            update(pos,i,(i+j)/2,p,q,si*2+1);
            update(pos,(i+j)/2+1,j,p,q,si*2+2);
        }
        else{
            return;
        }
    }

    public static void main(String args[])throws IOException{
        int i,j;
        br = new BufferedReader(new InputStreamReader(System.in));
        String s=next();
        int a[]=new int[s.length()];
        for(i=0;i<s.length();i++)
            a[i]=s.charAt(i)-97;
        A2 tree = new A2(); 
        int n=s.length();
        tree.constructST(a, n); 
        int q=nextInt();
        // for(i=0;i<y;i++){
        //         for(j=0;j<26;j++){
        //             pw.print(st2[i][j]+" ");
        //         }
        //         pw.println();
        //     }
        for(i=0;i<q;i++){
            int ai,b,c;
            ai=nextInt();
            b=nextInt()-1;
            if(ai==1){
                String jj=next();
                // System.out.println(jj);
                c=(jj.trim().charAt(0));
                c-=97;
                int b1=c;
                int b2=a[b];
                a[b]=b1;
                // pw.println(c);
                update(b,0,n-1,b1,b2,0);
            }
            else{
                c=nextInt()-1;
                int w=record(n,b,c);
                pw.println(w);
            }
            // for(i=0;i<y;i++){
            //     for(j=0;j<26;j++){
            //         pw.print(st2[i][j]+" ");
            //     }
            //     pw.println();
            // }
        }
        pw.close();
    }
}   




