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.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;
public class Main {

    public void sort(long b[]){
        Random rd = new Random();
        for(int i=1;i<b.length;++i){
            int c = rd.nextInt(i);
            long v = b[c];
            b[c] = b[i];
            b[i] = v;
        }
        Arrays.sort(b);
    }
    public void sort(int b[]){
        Random rd = new Random();
        for(int i = 1;i<b.length;++i){
            int c = rd.nextInt(i);
            int v = b[c];
            b[c]= b[i];
            b[i] = v;
        }
        Arrays.sort(b);
    }

    static int groups = 0;
    static int[] fa;
    static int[] sz;

    static void init(int n) {
        groups = n;
        fa = new int[n];
        for (int i = 1; i < n; ++i) {
            fa[i] = i;
        }
        sz = new int[n];
        Arrays.fill(sz, 1);
    }

    static int root(int p) {
        while (p != fa[p]) {
            fa[p] = fa[fa[p]];
            p = fa[p];
        }
        return p;
    }

    static void combine(int p, int q) {
        int i = root(p);
        int j = root(q);
        if (i == j) {
            return;
        }
        if (sz[i] < sz[j]) {
            fa[i] = j;
            sz[j] += sz[i];
        } else {
            fa[j] = i;
            sz[i] += sz[j];
        }
        groups--;
    }

    public static void main(String[] args) throws Exception {
        new Main().run();}

        void solve(){

        String s = ns();
        int len = s.length();
        long t[][] = new long[26][len+1];

        for(int i=1;i<=len;++i){
            int d = s.charAt(i-1)-'a';
            update(t[d],i,1);
        }
        char cs[] = s.toCharArray();

        int q = ni();
        for(int i=0;i<q;++i){
            int tp = ni();
            if(tp==1){
                int pos = ni();
                char d = nc();
                update(t[cs[pos-1]-'a'],pos,-1);
                update(t[d-'a'],pos,1);
                cs[pos-1] = d;
            }else{
                int l = ni()-1;
                int r =  ni();
                int c = 0;
                for(int j=0;j<26;++j){
                    long lef = get(t[j],l);
                    long ri = get(t[j],r);
                    if(ri-lef>0){
                        c++;
                    }
                }
                println(c);
            }

        }


//         PriorityQueue<int[]> q= new PriorityQueue<>((x,y)->{return x[0]-y[0];});
//
//         q.offer(new int[]{0,0});
//         boolean inq[] = new boolean[n];
//         while(q.size()>0){
//             int c[]= q.poll();
//             for(int i=h[c[1]];i!=-1;i=ne[i]){
//                 if(!inq[to[i]]) {
//                     q.offer(new int[]{ wt[i], to[i]});
//                     inq[to[i]] = true;
//                 }
//             }
//         }





        }


       int err = 0;



    void go(int rt,int pt,int fa) {
        stk[rt] = pt;
        for(int i=h[rt];i!=-1;i=ne[i]) {
            if(to[i]==pt||to[i]==fa) continue;
            go(to[i],pt,rt);
        }
    }



    int ct = 0;
    void add(int u,int v,int w,int q){
        to[ct] = v;
        wt[ct] = w;
        qt[ct] = q;
        ne[ct] = h[u];
        h[u] = ct++;
//
//        to1[ct] = u;
//        wt1[ct] = w;
//        ne1[ct] = h1[v];
//        h1[v] = ct++;
    }
    int []h,ne,to,wt,qt,stk;


    long inv(long a, long MOD) {
        //return fpow(a, MOD-2, MOD);
        return a==1?1:(long )(MOD-MOD/a)*inv(MOD%a, MOD)%MOD;
    }


    void inverse(){
        int MAXN = 10000;
        long inv[] = new long[MAXN+1];
        inv[1] = 1; //注意初始化
        long mod = 1000000007;
        for (int i=2; i<=MAXN; ++i) {
            inv[i] = (mod - mod / i) * inv[(int) (mod % i)] % mod;
        }
    }



    // 计算某个特别大的组合数
    long C(long n,long m, long MOD) {
        if(m+m>n)m=n-m;
        long up=1,down=1;
        for(long i=0;i<m;i++)
        {
            up=up*(n-i)%MOD;
            down=down*(i+1)%MOD;
        }
        return up*inv(down, MOD)%MOD;
    }


    void solve2() {

            int n = ni();
            String s=  ns();
            int g[][] = new int[3][3];
            for(int i = 0;i<n;++i){
                char c = s.charAt(i);
                int idx = 0;
                if(c=='G'){
                    idx =1;
                }else if(c=='B'){
                    idx =2;
                }
                g[c][i%3]++;
            }







        }































//    int []h,to,ne,wt;

    long t1[];
    //    long t2[];
    void update(long[] t,int i,long v){
        for(;i<t.length;i+=(i&-i)){
            t[i] += v;
        }
    }
    long get(long[] t,int i){
        long s = 0;
        for(;i>0;i-=(i&-i)){
            s += t[i];
        }
        return s;
    }

    int equal_bigger(long t[],long v){
        int s=0,p=0;
        for(int i=Integer.numberOfTrailingZeros(Integer.highestOneBit(t.length));i>=0;--i) {
            if(p+(1<<i)< t.length && s + t[p+(1<<i)] < v){
                v -= t[p+(1<<i)];
                p |= 1<<i;
            }
        }
        return p+1;
    }


    long gcd(long a,long b){ return b==0?a: gcd(b,a%b);}
    InputStream is;PrintWriter out;
    void run() throws Exception {is = System.in;
      //  is = new FileInputStream("C:\\Users\\Luqi\\Downloads\\P1600_2.in");

        out = new PrintWriter(System.out);solve();out.flush();}
    private byte[] inbuf = new byte[2];
    public int lenbuf = 0, ptrbuf = 0;
    private int readByte() {
        if (lenbuf == -1) throw new InputMismatchException();
        if (ptrbuf >= lenbuf) {
            ptrbuf = 0;
            try {lenbuf = is.read(inbuf);} catch (IOException e) {throw new InputMismatchException();}
            if (lenbuf <= 0) return -1;
        }
        return inbuf[ptrbuf++];}
    private boolean isSpaceChar(int c) {return !(c >= 33 && c <= 126);}
    private int skip() {int b;while((b = readByte()) != -1 && isSpaceChar(b));return b;}
    private double nd() {return Double.parseDouble(ns());}
    private char nc() {return (char) skip();}
    private char ncc() {int b;while((b = readByte()) != -1 && !(b >= 32 && b <= 126));return (char)b;}
    private String ns() {int b = skip();StringBuilder sb = new StringBuilder();
        while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);b = readByte(); }
        return sb.toString();}
    private char[] ns(int n) {char[] buf = new char[n];int b = skip(), p = 0;
        while (p < n && !(isSpaceChar(b))) { buf[p++] = (char) b;b = readByte(); }
        return n == p ? buf : Arrays.copyOf(buf, p);}
    private String nline() {int b = skip();StringBuilder sb = new StringBuilder();
        while (!isSpaceChar(b) || b == ' ') { sb.appendCodePoint(b);b = readByte(); }
        return sb.toString();}
    private char[][] nm(int n, int m) {char[][] a = new char[n][];for (int i = 0; i < n; i++) a[i] = ns(m);return a;}
    private int[] na(int n) {int[] a = new int[n];for (int i = 0; i < n; i++) a[i] = ni();return a;}
    private long[] nal(int n) { long[] a = new long[n];for (int i = 0; i < n; i++) a[i] = nl();return a;}
    private int ni() { int num = 0, b; boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')){};
        if (b == '-') { minus = true; b = readByte(); }
        while (true) {
            if (b >= '0' && b <= '9') num = (num << 3) + (num << 1) + (b - '0');
            else return minus ? -num : num;
            b = readByte();}}
    private long nl() { long num = 0; int b;
        boolean minus = false;
        while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')){};
        if (b == '-') { minus = true; b = readByte(); }
        while (true) {
            if (b >= '0' && b <= '9')  num = num * 10 + (b - '0');
            else return minus ? -num : num;
            b = readByte();}}
    void print(Object obj){out.print(obj);}
    void println(Object obj){out.println(obj);}
    void println(){out.println();}
}