Given an array $A$ of size $N$, support the $Q$ of the following operations:

1. Find the value and index of the smallest element from index $l$ to index $r$. If there are multiple smallest elements, find the index of the earliest one.
2. Update the element at index $i$ to value $x$.

Constraints

$1\le N,Q\le 2\times {10}^5$

$1\le l\le r\le N$

$1\le i\le N$

$1\le A_i,x\le {10}^9$

Input Specification

The first line contains $2$ integers $N$ and $Q$.

The second line contains $N$ integers $A_1,A_2,\dots ,A_N$, the initial elements of $A$.

The next $Q$ lines are one of two forms:

1. M l r representing the first operation.
2. U i x representing the second operation.

Output Specification

For each type $1$ operation output two integers, the minimum value and the leftmost index of that value in the given range.

Sample Input

5 5
6 3 3 2 4
M 2 4
M 2 3
U 2 6
M 1 2
M 1 3

Sample Output

2 4
3 2
6 1
3 3