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.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;

public class Main {


    long MODULO = 998244353;
    int INF = Integer.MAX_VALUE - 1234567;

    void solve() throws IOException {
        char[] s = readString().toCharArray();
        int[] arr = new int[s.length + 1];
        for (int i=0; i<s.length; ++i){
            arr[i + 1] = s[i] - 'a';
        }
        SegmentTree sgt = new SegmentTree(arr, s.length);
        int q = readInt();
        while (q-- > 0){
            int t = readInt();
            if (t == 1){
                int pos = readInt();
                int value = readString().toCharArray()[0] - 'a';
                sgt.update(1, 1, s.length, pos, value);
            }else{
                int l = readInt();
                int r = readInt();
                out.println(Long.bitCount(sgt.getSegment(1, 1, s.length, l, r)));
            }
        }
    }

    class SegmentTree{
        long[] t;
        int n;
        SegmentTree(int[] arr, int n){
            this.t = new long[n * 4];
            this.n = n;
            build(1, 1, n, arr);
        }

        int getLeft(int v){
            return  2*v;
        }
        int getRight(int v){
            return 2 * v + 1;
        }
        void build(int v, int tl, int tr, int[] arr){
            if (tl == tr){
                t[v] = 1l << arr[tl];
                return;
            }
            int mid = (tl + tr) / 2;
            int leftV = getLeft(v);
            int rightV = getRight(v);
            build(leftV, tl, mid, arr);
            build(rightV, mid+1, tr, arr);
            t[v] = t[leftV] | t[rightV];
        }

        void update(int v, int tl , int tr, int pos, int value){
            if (tl == tr){
                t[v] = 1 << value;
                return;
            }
            int mid = (tl + tr) / 2;
            int leftV = getLeft(v);
            int rightV = getRight(v);

            if (pos <= mid){
                update(leftV, tl, mid, pos, value);
            }else{
                update(rightV, mid + 1, tr, pos, value);
            }
            t[v] = t[leftV] | t[rightV];
        }

        long getSegment(int v, int tl, int tr, int l, int r){
            if (tl > r || tr < l) return 0;
            if (tl >= l && tr <= r){
                return t[v];
            }
            int mid = (tl + tr) / 2;
            int leftV = getLeft(v);
            int rightV = getRight(v);

            return getSegment(leftV, tl, mid, l, r) | getSegment(rightV, mid + 1, tr, l, r);
        }
    }
    long gcd(long a, long b){
        return a % b == 0 ? b : gcd(b, a % b);
    }

    int[][] steps = {{1, 0}, {0, 1}};
    String fileName = "";
    private final static Random rnd = new Random();
    boolean checkBit(long mask, int bit) {
        return (mask & (1l << bit)) > 0;
    }

    ////////////////////////////////////////////////////////////
    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        new Main().run();
    }

    void run() throws NumberFormatException, IOException {
        solve();
        out.close();
    }

    ;

    BufferedReader in;
    PrintWriter out;

    StringTokenizer tok;
    String delim = " ";

    Main() throws FileNotFoundException {
        try {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        } catch (Exception e) {
            if (fileName.isEmpty()) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader(fileName + ".in"));
                out = new PrintWriter(fileName + ".out");
            }

        }
        tok = new StringTokenizer("");
    }

    String readLine() throws IOException {
        return in.readLine();
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            String nextLine = readLine();
            if (null == nextLine) {
                return null;
            }

            tok = new StringTokenizer(nextLine);
        }
        return tok.nextToken(delim);
    }

    int readInt() throws NumberFormatException, IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws NumberFormatException, IOException {
        return Long.parseLong(readString());
    }

    int[] readIntArray(int n) throws NumberFormatException, IOException {
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            a[i] = readInt();
        }
        return a;
    }

    double readDouble() throws NumberFormatException, IOException {
        return Double.parseDouble(readString());
    }
}