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.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;
import java.util.function.BiFunction;

public class Main {
    long MOD = (long) 1e9 + 7;

    void run() {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        String s = sc.next();
        int q = sc.nextInt();

        SegmentTree[] sg = new SegmentTree[26];
        for (int i = 0; i < 26; i++) {
            sg[i] = new SegmentTree(n, Long::sum, 0);
        }

        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            int c = s.charAt(i) - 'a';
            a[i] = c;
            sg[c].update(i, 1);
        }

        PrintWriter out = new PrintWriter(System.out);

        for (int i = 0; i < q; i++) {
            int t = sc.nextInt();

            if (t == 1) {
                int iq = sc.nextInt() - 1;
                int c = sc.next().charAt(0) - 'a';
                if (a[iq] == c) continue;
                sg[c].update(iq, 1);
                sg[a[iq]].update(iq, 0);
                a[iq] = c;
            } else {
                int lq = sc.nextInt() - 1, rq = sc.nextInt();
                int cnt = 0;
                for (int j = 0; j < 26; j++) {
                    cnt += sg[j].query(lq, rq) > 0 ? 1 : 0;
                }
                out.println(cnt);
            }

        }

        out.flush();
    }

    public class SegmentTree {
        int n;
        long[] arr;
        BiFunction<Long, Long, Long> fn;
        long unity;

        SegmentTree(int n, BiFunction<Long, Long, Long> fn, long unity) {
            this.n = 1;
            while(this.n < n) {
                this.n *= 2;
            }
            arr = new long[2 * this.n - 1];
            this.fn = fn;
            this.unity = unity;
        }

        SegmentTree(int n) {
            this(n, Math::min, 1L << 60);
        }

        void update(int i, long x) {
            int k = this.n + i - 1;
            this.arr[k] = x;

            while (k > 0) {
                k = (k - 1) / 2;
                this.arr[k] = this.fn.apply(this.arr[2 * k + 1], this.arr[2 * k + 2]);
            }
        }

        long query(int l, int r) {
            return this.inneQuery(l, r, 0, 0, this.n);
        }

        private long inneQuery(int l, int r, int k, int il, int ir) {
            if (ir <= l || r <= il) {
                return this.unity;
            } else if(l <= il && ir <= r) {
                return this.arr[k];
            }

            long vl = this.inneQuery(l, r, k * 2 + 1, il, (il + ir) / 2);
            long vr = this.inneQuery(l, r, k * 2 + 2, (il + ir) / 2, ir);
            return this.fn.apply(vl, vr);
        }
    }

    void debug(Object... os) {
        System.err.println(Arrays.deepToString(os));
    }

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