You are given a string s consisting of lowercase Latin letters and q queries for this string.

Recall that the substring s[l; r] of the string s is the string s_l s_{l + 1} ... s_r. For example, the substrings of "codeforces" are "code", "force", "f", "for", but not "coder" and "top".

There are two types of queries: 

  * 1~ pos~ c (1 ≤ pos ≤ |s|, c is lowercase Latin letter): replace s_{pos} with c (set s_{pos} := c); 
  * 2~ l~ r (1 ≤ l ≤ r ≤ |s|): calculate the number of distinct characters in the substring s[l; r]. 

Input

The first line of the input contains one string s consisting of no more than 10^5 lowercase Latin letters.

The second line of the input contains one integer q (1 ≤ q ≤ 10^5) — the number of queries.

The next q lines contain queries, one per line. Each query is given in the format described in the problem statement. It is guaranteed that there is at least one query of the second type.

Output

For each query of the second type print the answer for it — the number of distinct characters in the required substring in this query.

Examples

Input


abacaba
5
2 1 4
1 4 b
1 5 b
2 4 6
2 1 7


Output


3
1
2


Input


dfcbbcfeeedbaea
15
1 6 e
1 4 b
2 6 14
1 7 b
1 12 c
2 6 8
2 1 6
1 7 c
1 2 f
1 10 a
2 7 9
1 10 a
1 14 b
1 1 f
2 1 11


Output


5
2
5
2
6

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.InputMismatchException;

public class D {
	private static int q, n;
	private static String s;
	private static int[] a;
	private static int[][] seg;

	public static void main(String[] args) {
		s = in.readString();
		q = ini();
		n = s.length();
		int m = 4*n;
		seg = new int[4*n][26];
		
		for(int i=0; i<n; i++) {
			update(i, s.charAt(i), 0, n-1, 0);
		}
//		int[] ans = query(0, n-1, 0, n-1, 0);
//		int count = 0;
//		for(int j=0; j<26; j++) {
//			println((char)(j+'a')+" "+ans[j]);
//			if (ans[j]!=0) count++;
//		}
//		println(count);
		
		
		for(int i=0; i<q; i++) {
			int type = ini();
			if (type==1) {
				int pos = ini()-1;
				char c = in.readString().charAt(0);
				update(pos, c, 0, n-1, 0);
			} else {
				int l = ini()-1;
				int r = ini()-1;
				int[] ans = query(l, r, 0, n-1, 0);
				int count = 0;
				for(int j=0; j<26; j++) {
//					println((char)(j+'a')+" "+ans[j]);
					if (ans[j]!=0) count++;
				}
				println(count);
				
			}
		}

		out.flush();
		out.close();

	}

	//NONPROBLEM CODE

	private static int[] query(int qlow, int qhigh, int low, int high, int pos) {
		if (qlow<=low && qhigh>=high) {
			return seg[pos];
		} else if (qhigh<low || high<qlow) {
			return new int[26];
		}
		int mid = (low+high)/2;
		int[] left = query(qlow, qhigh, low, mid, 2*pos+1);
		int[] right = query(qlow, qhigh, mid+1, high, 2*pos+2);
		
		int[] total = new int[26];
		for(int j=0; j<26; j++) {
			total[j] = left[j]+right[j];
		}
		return total;
	}

	private static void update(int index, char c, int low, int high, int pos) {
		if (low==high) {
			for(int i=0; i<26; i++) {
				if (seg[pos][i]!=0) {
					seg[pos][i] = 0;
					break;
				}
			}
			seg[pos][c-'a'] = 1;
			return;
		}
		int mid = (low+high)/2;
		
		if (index<=mid) {
			update(index, c, low, mid, 2*pos+1);
		} else {
			update(index, c, mid+1, high, 2*pos+2);
		}
		
		int[] left = seg[2*pos+1];
		int[] right = seg[2*pos+2];
		
		for(int j=0; j<26; j++) {
			seg[pos][j] = left[j]+right[j];
		}
		
	}

	private static InputReader in = new InputReader(System.in);
	private static PrintWriter out = new PrintWriter(System.out);

	private static class InputReader {

		private final InputStream stream;
		private final byte[] buf = new byte[8192];
		private int curChar, snumChars;

		public InputReader(InputStream st) {
			this.stream = st;
		}

		public int read() {
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

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

		public String readString() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		private boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

	}

	//INPUT SHORTCUTS

	private static int[] ina(int n) {
		int[] temp = new int[n];
		for (int i = 0; i < n; i++) {
			temp[i] = in.nextInt();
		}
		return temp;
	}

	private static int ini() {
		return in.nextInt();
	}

	//OTHER SHORTCUTS
	public static void sort(int[] a) {
		Arrays.sort(a);
	}

	//PRINT SHORTCUTS

	private static void println(Object... o) {
		for (Object x : o) {
			out.write(x + " ");
		}
		out.write("\n");
		out.flush();
	}

	private static void print(Object... o) {
		for (Object x : o) {
			out.write(x + " ");
		}
		out.flush();
	}

	private static void debug(Object... o) {
		for (Object x : o) {
			out.write(x + " ");
		}
		out.write("\n");
		out.flush();
	}

	private static HashMap<Integer, ArrayList<Integer>> intree(int n) {

		HashMap<Integer, ArrayList<Integer>> g = new HashMap<>();
		for (int i = 0; i < n; i++) {
			g.put(i, new ArrayList<>());
		}

		for (int i = 0; i < n - 1; i++) {
			int u = ini() - 1;
			int v = ini() - 1;
			g.get(u).add(v);
			g.get(v).add(u);
		}

		return g;
	}
}
