Problem Description
Peanut is sitting in his Biology class, bored to death. Learning about DNA mutations today, he scribbles down N 'A's on a piece of papers and wonders, what if I randomly "mutate" any range of DNA into another base pair, such as 'T'? What would the DNA string become then? He then formalises this procedure, by denoting two operations:
- A mutate operation, which will be in the input format 1 x y c, which means a mutation from positions x to y (0-indexed, inclusive) to base pair c.
- An ask operation, which will be in the input format 2 x, which queries for the base pair at position x (0-indexed).
Given Q queries, help Peanut answer all "ask" operations correctly by outputting the base pair on a seperate line for each "ask" operation.
Input
The first line of input will contain two integers, N and Q.
The next Q lines of input will contain either a "mutate" or "ask" operation in the format above.
Output
Your output should contain one letter on a line for each "ask" operation.
Limits
1 ≤ N ≤ 1 000 000 000. 1 ≤ Q ≤ 300 000.
Subtask 1 (16%): The DNA string will only contain 'A' and 'T'.
Subtask 2 (17%): 1 ≤ N ≤ 1000. 1 ≤ Q ≤ 3000.
Subtask 3 (18%): 1 ≤ N ≤ 1 000 000.
Subtask 4 (49%): No other constraints apply.
Subtask 5 (0%): Sample testcases.
Sample Input 1
5 4
1 1 3 C
1 2 4 T
2 2
2 0
Sample Output 1
T
A
Sample Input 2
10 6
1 4 8 G
1 0 2 C
2 2
1 2 5 T
2 2
2 9
Sample Output 2
C
T
A