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.*;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.security.KeyStore.Entry;
import java.text.DecimalFormat;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import javax.net.ssl.SSLContext;

public class Main
{ 
	
   static long mod=(long)(1e+9 + 7);
   static int[] sieve;
   static ArrayList<Integer> primes;
   static int[] visited;
   static String ans;
   
   static class Tree
   {
   	boolean freq[]=new boolean[26];
   	 
   	public Tree()
   	{
   		Arrays.fill(this.freq, false);
   	}	
   	public Tree(char ch)
   	{
   		this.freq[ch-'a']=true;
   	}	
   	
   	public void setval(char ch)
   	{
   		this.freq[ch-'a']=true;
   	}
   	
   	public void merge(Tree left,Tree right)
   	{
   		for(int i=0;i<26;i++)
   			this.freq[i]=left.freq[i] || right.freq[i];
   	}	
   }
   
   static String str;
   static Tree tree[];
   
   public static void build(int n,int start,int end,int size)
	   {
		   int mid=(start+end)>>1;
		   
		   if(start==end && start>size) 
		   {
			   tree[n]=new Tree();
			   return;
		   }
		   if(start==end)
		   {
			   tree[n]=new Tree(str.charAt(start-1));
			   return;
		   }
		   
		   build(n<<1,start,mid,size);
		   build((n<<1) + 1,mid+1,end,size);
		   
		   tree[n]=new Tree();
		   tree[n].merge(tree[n<<1], tree[(n<<1) + 1]);
	   }
	   
	   public static Tree query(int n,int start,int end,int l ,int r)
	   {
		   int mid=(start+end)>>1;
		   
		   if(start >=l && end<=r) return tree[n];
		   else if(start > r || end<l) return null;
		   
		   Tree left=null, right=null;
		   
		   if(l<=mid) 
			   left=query(n<<1,start,mid,l,r);
		   if(r>mid)
			   right=query((n<<1) + 1,mid+1,end,l,r);
		   
		   if(left==null) return right;
		   if(right==null) return left;
		   
		   Tree t=new Tree();
		   t.merge(left, right);
		   
		   return t;
	   }
	   
	   public static void update(int n,int start,int end, int ind,char ch)
	   {
		   int mid=(start+end)>>1;
		   
		   if(start==end) 
			   {
				   Arrays.fill(tree[n].freq,false);
				   tree[n].setval(ch); 
				   return;
			   }
		   
		   if(ind>=start && ind<=mid) update((n<<1),start,mid,ind,ch);	 
		   if(ind > mid && ind<=end) update((n<<1) + 1,mid+1,end,ind,ch);
		   
		   tree[n].merge(tree[n<<1],tree[(n<<1) + 1]);
	   }
	   
   public static void main(String[] args) throws java.lang.Exception
   {	  	
	     fast s = new fast();
	     PrintWriter out=new PrintWriter(System.out);
	     StringBuilder fans=new StringBuilder("");
	         
	     str=s.nextLine();
	     int n=str.length(); 
	     int MAXN;
		   
	       
	        int max = n;
			 max |= (max >> 1);
			 max |= (max >> 2);
			 max |= (max >> 4);
			 max |= (max >> 8);
			 max |= (max >> 16);
			 max = max+1;

			tree = new Tree[2*max+1];
		
	       build(1,1,max,n);
	       
	       int q=s.nextInt();
	       
	       for(int x=1;x<=q;x++)
	    	   {
	    		   int type=s.nextInt();
	    		   
	    		   if(type==2)
	    			   {
			    		   int l=s.nextInt();
			    		   int r=s.nextInt();
			    		   Tree a=query(1,1,max,l,r);
			    		   int cnt=0;
			    		   
			    	       for(int k=0;k<26;k++)
			    	    	   if(a.freq[k]==true)
			    	    		   cnt++;
			    	       
			    	       fans.append(cnt+"\n");
	    			   }
	    		   else
	    			   {
	    				   String full=s.nextLine();
	    				   String ss[]=full.split(" ");
	    				   
	    				   int ind=Integer.parseInt(ss[0]);
	    				   char val=ss[1].charAt(0);
	    				   
	    				   update(1,1,max,ind,val);
	    			   }
	    	   }
	       out.println(fans);
	       out.close();
   }
  
 

static class fast {   
	private InputStream i;
		private byte[]  buf = new byte[1024];
		private int curChar;
		private int numChars;
		
		//Return floor log2n
		public static long log2(long bits) // returns 0 for bits=0
			{
			    int log = 0;
			    if( ( bits & 0xffff0000 ) != 0 ) { bits >>>= 16; log = 16; }
			    if( bits >= 256 ) { bits >>>= 8; log += 8; }
			    if( bits >= 16  ) { bits >>>= 4; log += 4; }
			    if( bits >= 4   ) { bits >>>= 2; log += 2; }
			    return log + ( bits >>> 1 );
			}
		
		public static boolean next_permutation(int a[])
		   {
			   int i=0,j=0;int index=-1;	   
			   int n=a.length;
			   
			   for(i=0;i<n-1;i++)
				   if(a[i]<a[i+1]) index=i;
			   
			   if(index==-1) return false;
			   i=index;

			  
			   for(j=i+1;j<n && a[i]<a[j];j++);

			   int temp=a[i];
			   a[i]=a[j-1];
			   a[j-1]=temp;
			   	   
			   for(int p=i+1,q=n-1;p<q;p++,q--)
			   {
				   temp=a[p];
				   a[p]=a[q];
				   a[q]=temp;
			   }
			   
			   return true;
		   }
		   
		   
		public static void division(char ch[],int divisor)
		   {
			   int div=Character.getNumericValue(ch[0]); int mul=10;int remainder=0;
			   StringBuilder quotient=new StringBuilder("");
			   for(int i=1;i<ch.length;i++)
			   {
				   div=div*mul+Character.getNumericValue(ch[i]);	
				   if(div<divisor) {quotient.append("0");continue;}
				   quotient.append(div/divisor);
				   div=div%divisor;mul=10;
				   
			   } 
			   remainder=div;
			   while(quotient.charAt(0)=='0')quotient.deleteCharAt(0);	   
			   System.out.println(quotient+" "+remainder);	  
		   }
		
		public static void sieve(int size)
		{
			sieve=new int[size+1];
			
			primes=new ArrayList<Integer>();
			
			sieve[1]=1;
			
			for(int i=2;i<=Math.sqrt(size);i++)
			{
				if(sieve[i]==0)
				 {
					for(int j=i*i;j<size;j+=i) {sieve[j]=1;}
				 }
			}
			
			for(int i=2;i<=size;i++)
			{
				if(sieve[i]==0) primes.add(i);
			}
		}
		
		public static long pow(long n, long b, long MOD)
		   {
		       long x=1;long y=n; 
		       while(b > 0)
		       {
		           if(b%2 == 1)
		           {
		               x=x*y;
		               if(x>MOD) x=x%(MOD);
		           }
		           y = y*y;
		           if(y>MOD) y=y%(MOD); 
		           b >>= 1;
		       }
		       return x;
		   }


		public static long mod_inv(long n,long mod)
		{
			return pow(n,mod-2,mod);
		}
		
		//Returns index of highest number less than or equal to key
		 public static int upper(long[] a,int length,long key)
		 {
			    int low = 0;
		        int high = length-1;
		        int ans=-1;
		        
		        while (low <= high) {
		            int mid = (low + high) / 2;
		            if (key >= a[mid]) {
		                ans=mid;
		            	low = mid+1;
		            } else if(a[mid]>key){
		                high = mid - 1;
		            }
		        }
		        return ans;
		}
		
		//Returns index of least number greater than or equal to key
		 public static int lower(long[] a,int length,long key)
		 {
			    int low = 0;
		        int high = length-1;
		        int ans=-1;
		        
		        while (low <= high) {
		            int mid = (low + high) / 2;
		            if (key<=a[mid]) {
		                ans=mid;
		            	high = mid-1;
		            }
		            else{
		            		low=mid+1;
		            	}
		        }
		        return ans;
		} 
		   
		public long gcd(long r,long ans)
		{
			if(r==0) return ans;
			return gcd(ans%r,r);
		}
		public fast() {
			this(System.in);
		}
		public fast(InputStream is) {
			i = is;
		}
		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = i.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
		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 String nextString() {
     		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 long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
		public boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

	}	
}