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
//--- pE ---//
import java.util.*;
import java.lang.*;
import java.io.*;
public class Main {
	public static void main (String[] args) throws java.lang.Exception {
		new Solution();
	}
}
class Solution {
	Reader reader;
	public Solution () {
		reader = new Reader();
		while (reader.hasNext()) {
			run_case();
		}
	}
	private void run_case() {
		int N = ni();
		String str = ns();

		List<BIT> list_st = new ArrayList<>();
		for (int i=0; i<26; i++) list_st.add(new BIT(N+1));
		// SegmentTreeRSQ st = new SegmentTreeRSQ(1, N);
		for (int i=0; i<str.length(); i++) {
			int idx = str.charAt(i) - 'a';
			// int t = (int)list_st.get(idx).query(i + 1, i + 1);
			list_st.get(idx).addVal(i, 1);
		}

		int Q = ni();
		StringBuilder str_sb = new StringBuilder(str);
		for (;Q-->0;) {
			// int[] arr = strToIntArray(scanner.nextLine());
			// String[] vals = scanner.nextLine().split("\\s+");

			int q = ni();

			if (q == 1) {
				int i = ni();
				char c = ns().charAt(0);
				int n = str_sb.charAt(i-1) - 'a';
				int m = c - 'a';

				// int t = (int)list_st.get(n).query(i, i);
				list_st.get(n).addVal(i-1, -1);

				str_sb.setCharAt(i-1, c);

				// t = (int)list_st.get(m).query(i, i);
				list_st.get(m).addVal(i-1, 1);
			} else {
				int l = ni()-1;
				int r = ni()-1;
				int cnt = 0;
				for (int i=0; i<26; i++) {
					if (list_st.get(i).getSum(l, r) > 0) cnt ++;
				}
				System.out.println(cnt);
			}
		}
		return;
	}
	private int ni() {return Integer.parseInt(reader.next());}
	private String ns() {return reader.next();}
}

class Reader {
	BufferedReader br;
	StringTokenizer st;
	public Reader(){
		try {
			br = new BufferedReader(new InputStreamReader(System.in));
			st = new StringTokenizer(br.readLine());
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	public String next() {
		if (st.hasMoreTokens()) return st.nextToken();
		try {
			st = new StringTokenizer(br.readLine());
		} catch (Exception e) {
			e.printStackTrace();
		}
		return st.nextToken();
	}
	public boolean hasNext() {
		try {
			if (!st.hasMoreTokens() && !br.ready()) return false;
			else return true;
		} catch (Exception e) {
			e.printStackTrace();
		}
		return false;
	}
}

class BIT {
	public long[] arr;
	public BIT(int n) {
		arr = new long[n];
	}
	public long getSum(int i) {
		long sum = 0;
		for(i++;i > 0;i -= i&-i)sum += arr[i];
		return sum;
	}
	public long getSum(int l, int r) {
		return getSum(r) - getSum(l-1);
	}
	public void addVal(int i, long v) {
		if(v == 0)return;
		int n = arr.length;
		for(i++;i < n;i += i&-i)arr[i] += v;
	}
}
