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, \ldots, 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