#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 16 | 20 | 1.5s | 256MB | Minimum |

2 | 17 | 20 | 1.5s | 256MB | Minimum |

3 | 18 | 20 | 1.5s | 256MB | Minimum |

4 | 49 | 20 | 1.5s | 256MB | Minimum |

5 | 0 | 2 | 1.5s | 256MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o mutations -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512