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.util.Arrays;
import java.util.StringJoiner;
import java.util.StringTokenizer;

public class MainD {

    public static void main(String[] args) {
        FastScanner sc = new FastScanner(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        char[] S = sc.next().toCharArray();
        int N = S.length;

        FenwickTree[] bits = new FenwickTree[26];
        for (int i = 0; i < 26; i++) {
            bits[i] = new FenwickTree(N+10, FenwickTree.SUM);
        }
        for (int i = 0; i < N; i++) {
            char c = S[i];
            bits[c-'a'].add(i, 1);
        }

        int Q = sc.nextInt();
        for (int q = 0; q < Q; q++) {
            int t = sc.nextInt();
            if( t == 1 ) {
                int pos = sc.nextInt()-1;
                char c = sc.next().charAt(0);
                char d = S[pos];
                bits[d-'a'].add(pos, -1);
                bits[c-'a'].add(pos, 1);
                S[pos] = c;

            } else {
                int l = sc.nextInt();
                int r = sc.nextInt();
                int cnt = 0;
                for (int i = 0; i < 26; i++) {
                    long sum = bits[i].query(l-1, r);
                    if( sum > 0 ) {
                        cnt++;
                    }
                }
                pw.println(cnt);
            }
        }

        pw.flush();
    }

    static int solve() {

        return -1;
    }

    static class FenwickTree {

        interface Monoid {
            long identity();
            long apply(long a, long b);
            long inverse(long a);
        }

        static Monoid SUM = new Monoid() {
            public long identity() { return 0; }
            public long apply(long a, long b) { return a+b; }
            public long inverse(long a) { return -a; }
        };

        static Monoid MAX = new Monoid() {
            public long identity() { return 0; }
            public long apply(long a, long b) { return Math.max(a, b); }
            public long inverse(long a) { throw new RuntimeException("no inverse"); }
        };


        int size;
        long[] bit;
        Monoid m;
        long identity;

        FenwickTree(int size, Monoid m) {
            this.size = 1;
            while( this.size < size ) this.size *= 2;
            this.bit = new long[this.size+1];
            this.identity = m.identity();
            if( this.identity != 0 ) {
                Arrays.fill(this.bit, this.identity);
            }
            this.m = m;
        }

        void add(int i, long v) {
            i++; // 0 index -> 1 index

            while( i <= size ) {
                bit[i] = m.apply(bit[i], v);
                i += i & -i;
            }
        }

        // [0, r)
        long query(int r) {
            // 0 index -> 1 index -> -1
            long ret = identity;
            while(r > 0) {
                ret = m.apply(ret, bit[r]);
                r -= r & -r;
            }
            return ret;
        }

        long query(int l, int r) {
            return query(r) + m.inverse(query(l));
        }

        int lowerBound(int v) {
            if( bit[size] < v ) return size;

            int x = 0;
            for (int k = size/2; k > 0; k /= 2 ) {
                if( bit[x + k] < v ) {
                    v -= bit[x+k];
                    x += k;
                }
            }
            return x;
        }
    }

    @SuppressWarnings("unused")
    static class FastScanner {
        private BufferedReader reader;
        private StringTokenizer tokenizer;

        FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken("\n");
        }

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

        int nextInt() {
            return Integer.parseInt(next());
        }

        int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        int[] nextIntArray(int n, int delta) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt() + delta;
            return a;
        }

        long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++) a[i] = nextLong();
            return a;
        }
    }

    static void writeLines(int[] as) {
        PrintWriter pw = new PrintWriter(System.out);
        for (int a : as) pw.println(a);
        pw.flush();
    }

    static void writeLines(long[] as) {
        PrintWriter pw = new PrintWriter(System.out);
        for (long a : as) pw.println(a);
        pw.flush();
    }

    static void writeSingleLine(int[] as) {
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < as.length; i++) {
            if (i != 0) pw.print(" ");
            pw.print(as[i]);
        }
        pw.println();
        pw.flush();
    }

    static int max(int... as) {
        int max = Integer.MIN_VALUE;
        for (int a : as) max = Math.max(a, max);
        return max;
    }

    static int min(int... as) {
        int min = Integer.MAX_VALUE;
        for (int a : as) min = Math.min(a, min);
        return min;
    }

    static void debug(Object... args) {
        StringJoiner j = new StringJoiner(" ");
        for (Object arg : args) {
            if (arg == null) j.add("null");
            else if (arg instanceof int[]) j.add(Arrays.toString((int[]) arg));
            else if (arg instanceof long[]) j.add(Arrays.toString((long[]) arg));
            else if (arg instanceof double[]) j.add(Arrays.toString((double[]) arg));
            else if (arg instanceof Object[]) j.add(Arrays.toString((Object[]) arg));
            else j.add(arg.toString());
        }
        System.err.println(j.toString());
    }

    static void printSingleLine(int[] array) {
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < array.length; i++) {
            if (i != 0) pw.print(" ");
            pw.print(array[i]);
        }
        pw.println();
        pw.flush();
    }

    static int lowerBound(int[] array, int value) {
        int lo = 0, hi = array.length, mid;
        while (lo < hi) {
            mid = (hi + lo) / 2;
            if (array[mid] < value) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }

    static int upperBound(int[] array, int value) {
        int lo = 0, hi = array.length, mid;
        while (lo < hi) {
            mid = (hi + lo) / 2;
            if (array[mid] <= value) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}
