Joe loves bubble tea. However, he hates spending money, so he always buys the cheapest product. His favourite chain, Bubble tea and me, has a set of ~N~ bubble tea items with a corresponding price and product number from ~[1, N]~. They will also occasionally replace items. Their menu displays a set of items with consecutive product numbers from ~l~ to ~r~ inclusive. Given the original prices, product replacements and items displayed, find the cheapest bubble tea item available whenever Joe visits the store.

Input Specification

The first line contains two space-separated numbers ~N \ (1\leq N \leq 100\,000)~, the number of bubble tea items and ~M \ (1\leq M\leq 100\,000)~, the amount of operations (product replacements and store visits).

The next ~N~ lines contain the price of the bubble tea items with the price on line ~i~ representing the price of item ~i-1~. The price will always be a non-negative integer no greater than ~1\,000\,000~.

The next ~M~ lines contain one operation each. Each operation has the form of either M i x where product number ~i \ (1< i\leq N)~ is replaced with a product with price ~x \ (0\leq x< 1\,000\,000)~, or Q l r ~1\leq l \leq r \leq N~ indicating products ~[l,r]~ are on display for Joe to buy from.

Output Specification

For each Q Query, output the cheapest bubble tea item available.

Subtasks

Subtask 1 [30%]

~1\leq N\leq 100~

~1\leq M\leq 100~

Subtask 2 [70%]

No further restrictions

Sample Input

5 10
35232
390942
649675
224475
18709
Q 2 4
M 5 475689
Q 3 4
Q 2 4
Q 2 3
Q 4 4
Q 3 4
M 3 645514
M 3 680746
Q 1 5

Sample Output

224475
224475
224475
390942
224475
224475
35232