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

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		String str = sc.next();
		int q = sc.nextInt();
		
		SqrtDecompositionROQRUQ sq = new SqrtDecompositionROQRUQ(n);
		for(int i = 0; i < n; i++) {
			char c = str.charAt(i);
			sq.update(i, i + 1, 1 << (int)(c - 'a'));
		}
		
		for(int i = 0; i < q; i++) {
			int inst = sc.nextInt();
			
			if(inst == 1) {
				int index = sc.nextInt() - 1;
				char c = sc.next().charAt(0);
				sq.update(index, index + 1, 1 << (int)(c - 'a'));
			}
			else {
				int l = sc.nextInt() - 1;
				int r = sc.nextInt() - 1;
				
				long or = sq.getSum(l, r + 1);
				
//				System.out.printf("%x\n", or);
				int count = 0;
				while(or > 0) {
					if(or%2 == 1) {
						count++;
					}
					or /= 2;
				}
				System.out.println(count);
			}
//			for(int j = 0; j < n; j++) {
//				System.out.print(sq.get(j) + " ");
//			}
//			System.out.println();
		}

	}

}

class SqrtDecompositionROQRUQ {
	int N, K;
	long[] data;
	long[] bucketOr;
	long[] bucketLazyUpdate;
	static final int sqrtN = 512;
	static final int NIL = Integer.MIN_VALUE;

	public SqrtDecompositionROQRUQ(int n) {
		N = n;
		K = (N + sqrtN - 1) / sqrtN;
		data = new long[K * sqrtN];
		bucketLazyUpdate = new long[K];
		Arrays.fill(bucketLazyUpdate, NIL);
		bucketOr = new long[K];
	}

	// [s, t)
	void update(int s, int t, int x) {
		for (int k = 0; k < K; ++k) {
			int l = k * sqrtN, r = (k + 1) * sqrtN;
			if (r <= s || t <= l)
				continue;
			if (s <= l && r <= t) {
				bucketLazyUpdate[k] = x;
				bucketOr[k] = x;
			} else {
				if(bucketLazyUpdate[k] != NIL){
					for(int i = l; i < r; i++){
						data[i] = bucketLazyUpdate[k];

					}
					bucketLazyUpdate[k] = NIL;
				}
				for (int i = Math.max(s, l); i < Math.min(t, r); ++i) {
					data[i] = x;
				}
				bucketOr[k] = 0;
				for(int i = l; i < r; i++){
					bucketOr[k] |= data[i];
				}
			}
		}
	}

	//[s,t)
	long getSum(int s, int t) {
		long result = 0;
		for (int k = 0; k < K; ++k) {
			int l = k * sqrtN, r = (k + 1) * sqrtN;
			if (r <= s || t <= l)
				continue;
			if (s <= l && r <= t) {
				result |= bucketOr[k];
			}
			else {
				for (int i = Math.max(s, l); i < Math.min(t, r); ++i) {
					if(bucketLazyUpdate[k] != NIL){
						result |= bucketLazyUpdate[k];
					}
					else {
						result |= data[i];
					}
				}
			}
		}

		return result;
	}

	long get(int s) {
		int k = s / sqrtN;
		if(bucketLazyUpdate[k] != NIL){
			return bucketLazyUpdate[k];
		}
		else {
			return data[s];
		}
	}
}