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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;

class Main {
    static final int MOD = 1000000007;
    static final int INF = 1 << 30;

    Main() {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        char[] S = sc.next().toCharArray();
        int Q = sc.nextInt();
        SegmentSum[] alf = new SegmentSum[27];
        for (int i = 0; i < 27; i++) {
            alf[i] = new SegmentSum(N);
        }
        for (int i = 0; i < N; i++) {
            alf[S[i] - 'a'].update(i, 1);
        }
        for (int q = 0; q < Q; q++) {
            if (sc.next().equals("1")) {
                int p = sc.nextInt() - 1;
                char c = sc.next().charAt(0);
                alf[S[p] - 'a'].update(p, 0);
                alf[c - 'a'].update(p, 1);
                S[p] = c;
            } else {
                int a = sc.nextInt() - 1;
                int b = sc.nextInt() - 0;
                int ans = 0;
                for (int i = 0; i < 27; i++) {
                    int sum = alf[i].getSum(a, b);
                    if (sum > 0) {
                        ans++;
                    }
                }
                System.out.println(ans);
            }
        }
    }

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

class SegmentSum {
    int[] data;
    int size;
    int rawsize;
    int rawindex;

    SegmentSum(int size) {
        this.size = size;
        int n = 2;
        while (n < size)
            n <<= 1;
        rawsize = n;
        rawindex = n - 1;
        n = n * 2 - 1;
        data = new int[n];
    }

    void update(int index, int val) {
        data[rawindex + index] = val;
        innerUpdate((rawindex + index - 1) / 2);
    }

    private void innerUpdate(int index) {
        data[index] = data[index * 2 + 1] + data[index * 2 + 2];
        if (index == 0)
            return;
        innerUpdate((index - 1) / 2);
    }

    int getSum(int left, int right) {
        return innerGetSum(left, right, 0, 0, rawsize);
    }

    private int innerGetSum(int left, int right, int index, int l, int r) {
        if (r <= left || right <= l)
            return 0;
        if (left <= l && r <= right)
            return data[index];
        int lm = innerGetSum(left, right, index * 2 + 1, l, (l + r) / 2);
        int rm = innerGetSum(left, right, index * 2 + 2, (l + r) / 2, r);
        return lm + rm;
    }

    int getAt(int index) {
        return data[rawindex + index];
    }
}

class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;

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

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

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

        return tokenizer.nextToken("\n");
    }

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

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

    public double nextDouble() {
        return Double.parseDouble(next());
    }

    public ArrayList<Integer> nextIntList(int n) {
        ArrayList<Integer> a = new ArrayList<Integer>(n);
        for (int i = 0; i < n; i++)
            a.add(nextInt());
        return a;
    }

    public ArrayList<Long> nextLongList(int n) {
        ArrayList<Long> a = new ArrayList<Long>(n);
        for (int i = 0; i < n; i++)
            a.add(nextLong());
        return a;
    }

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

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