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
// Don't place your source in a package

import java.math.BigInteger;
import java.util.*;
import java.lang.*;
import java.io.*;



// Please name your class Main
public class Main {
    static FastScanner fs=new FastScanner();
    static class FastScanner {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer("");
        public String next() {
            while (!st.hasMoreElements())
                try {
                    st=new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            return st.nextToken();
        }
        int Int() {
            return Integer.parseInt(next());
        }

        long Long() {
            return Long.parseLong(next());
        }

        String Str(){
            return next();
        }
    }


    public static void main (String[] args) throws java.lang.Exception {
        PrintWriter out = new PrintWriter(System.out);


        int T=1;
        for(int t=0;t<T;t++){
            String s=Str();
            int m=Int();
            int q[][]=new int[m][3];
            for(int i=0;i<q.length;i++){
                q[i][0]=Int();
                q[i][1]=Int()-1;
                if(q[i][0]==1){
                    q[i][2]=Str().charAt(0)-'a';
                }
                else{
                    q[i][2]=Int()-1;
                }
            }

            Solution sol=new Solution(out);
            sol.solution(s,q);
        }
        out.flush();

    }


    public static int Int(){
        return fs.Int();
    }
    public static long Long(){
        return fs.Long();
    }
    public static String Str(){
        return fs.Str();
    }

}






class Solution{
    PrintWriter out;
    public Solution(PrintWriter out){
        this.out=out;
    }


    public void solution(String s,int q[][]){
        int A[]=new int[s.length()];
        for(int i=0;i<s.length();i++){
            A[i]=s.charAt(i)-'a';
        }

        TreeSet<Integer>sets[]=new TreeSet[26];
        for(int i=0;i<sets.length;i++){
            sets[i]=new TreeSet<>();
        }

        for(int i=0;i<A.length;i++){
            sets[A[i]].add(i);
        }

        for(int p[]:q){
            if(p[0]==1){
                int pos=p[1],val=p[2];
                sets[A[pos]].remove(pos);
                A[pos]=val;
                sets[val].add(pos);
            }
            else{
                int cnt=0;
                for(int j=0;j<sets.length;j++){
                    Integer floor=sets[j].floor(p[2]);
                    if(floor!=null&&floor>=p[1]){
                        cnt++;
                    }
                }
                out.println(cnt);
            }
        }

    }




}



/*
                             ;\
                            |' \
         _                  ; : ;
        / `-.              /: : |
       |  ,-.`-.          ,': : |
       \  :  `. `.       ,'-. : |
        \ ;    ;  `-.__,'    `-.|
         \ ;   ;  :::  ,::'`:.  `.
          \ `-. :  `    :.    `.  \
           \   \    ,   ;   ,:    (\
            \   :., :.    ,'o)): ` `-.
           ,/,' ;' ,::"'`.`---'   `.  `-._
         ,/  :  ; '"      `;'          ,--`.
        ;/   :; ;             ,:'     (   ,:)
          ,.,:.    ; ,:.,  ,-._ `.     \""'/
          '::'     `:'`  ,'(  \`._____.-'"'
             ;,   ;  `.  `. `._`-.  \\
             ;:.  ;:       `-._`-.\  \`.
              '`:. :        |' `. `\  ) \
      -hrr-      ` ;:       |    `--\__,'
                   '`      ,'
                        ,-'


                      free bug dog
*/





