Long assumes herself (here Long is a girl) a good programmer...
She was reading DISJOINT SET UNION. Somehow, her counterpart Circuit comes to know about this and arranges a trap for Long.
Long is asked a question.
She is given a string S (made of lowercase letters) and Q queries will be asked over the string.
EACH QUERY is of 3 types.
3 Integers is given as input for type 1 i.e b,c,k. You have to tell the character at the kth position when all the characters from indices b to c (both inclusive) in String S(indexing is 0 based) are used to make the lexicographically largest string of size c-b+1.
Note: s1 and s2 are two equal string and s2 is lexicoraphically greater than s1 iff the character at first point of difference in s2 has HIGHER ASCII Value. E.g. uyz > uxz since y>x.
1 Integer b and 1 character x is given as input in type 2. You have to change the character at bth index in updated String with character x.
You will be given 2 Integers b,c and 2 characters x,y. In this query, you have to change all the characters which are equal to x in range b to c (both index inclusive in updated string) to character y.
Note:- After each query of type 2 and 3, we get the updated string and further queries are to be done over the updated string.
Each Query has either 4 Integer (a,b,c,k with a=1 for type 1) or 2 Integer with 1 character (a,b,x with a=2 for type 2) or 3 integers (a,b,c with a=3 for type 3) and 2 characters x,y.
For each query of type 1 , tell the character at kth place.