You are given a string S of length N consisting of lowercase English letters.

Process Q queries of the following two types:

* Type 1: change the i_q-th character of S to c_q. (Do nothing if the i_q-th character is already c_q.)
* Type 2: answer the number of different characters occurring in the substring of S between the l_q-th and r_q-th characters (inclusive).

Constraints

* N, Q, i_q, l_q, and r_q are integers.
* S is a string consisting of lowercase English letters.
* c_q is a lowercase English letter.
* 1 \leq N \leq 500000
* 1 \leq Q \leq 20000
* |S| = N
* 1 \leq i_q \leq N
* 1 \leq l_q \leq r_q \leq N
* There is at least one query of type 2 in each testcase.

Input

Input is given from Standard Input in the following format:


N
S
Q
Query_1
\vdots
Query_Q


Here, Query_i in the 4-th through (Q+3)-th lines is one of the following:


1 i_q c_q



2 l_q r_q


Output

For each query of type 2, print a line containing the answer.

Example

Input

7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7


Output

3
1
5
import java.util.*;

public class Main{

    Scanner sc = new Scanner(System.in);

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

    void run() {
        int n = sc.nextInt();
        char[] arr = sc.next().toCharArray();
        int q = sc.nextInt();

        StringBuffer sb = new StringBuffer();

        SegTree st = new SegTree(n);

        for (int i=0; i<n; i++) {
            st.update(i, arr[i] - 'a');
        }

        for (int i=0; i<q; i++) {
            int t = sc.nextInt();
            if (t == 1) {
                int idx = sc.nextInt() - 1;
                char c = sc.next().charAt(0);
                st.update(idx, c - 'a');
            } else {
                int l = sc.nextInt() - 1;
                int r = sc.nextInt() - 1;
                int u = st.query(l, r + 1);
                sb.append( Integer.bitCount(u)+ "\n");
            }
        }

        System.out.println(sb.toString());
    }

    public class SegTree {

        int n = 1;
        int[] val;

        public SegTree(int n) {
            while (this.n < n) this.n *= 2;
            val = new int[2*this.n-1];
        }

        void update(int k, int a) {
            k += n - 1;
            val[k] = (1 << a);
            while (k > 0) {
                k = (k - 1) / 2;
                val[k] = val[2*k+1] | val[2*k+2];
            }
        }

        int query(int a, int b) {
//            for (int i=0; i<val.length; i++) {
//                System.out.println(val[i]);
//            }
            return query(0, n, a, b, 0);
        }

        int query(int l, int r, int a, int b, int k) {
            if (r<=a || b<=l) return 0;
            if (a<=l && r<=b) return val[k];
            else {
                int vl = query(l, (l+r)/2, a, b, 2*k+1);
                int vr = query((l+r)/2, r, a, b, 2*k+2);
                return vl | vr;
            }
        }
    }

}
