Maximum of a Changing Segment

A weather service keeps $n$ sensors in a row along a mountain road, numbered $0$ to $n-1$, and every sensor reports one temperature.

Two things happen during the day, over and over:

• a forecaster asks for the highest temperature reported by the sensors on some stretch of road,
• a sensor is recalibrated and its reading is replaced by a new one.

Write a program that answers every question, using the readings as they are at that moment.

Input

First line of input will be a single integer $t$ - the number of testcases.
The first line of each testcase contains two integers $n$ and $q$ - the number of sensors and the number of events.
The second line contains $n$ integers $v_0,v_1,\dots ,v_{n-1}$ - the readings the sensors start with.
Each of the next $q$ lines describes one event, in one of two forms:

• a l r - print the highest reading among sensors $l,l+1,\dots ,r$;
• b i x - sensor $i$ is recalibrated, its reading becomes $x$.

Sensors are numbered from $0$, so $l$, $r$ and $i$ are all between $0$ and $n-1$.

Output

For every event of type a, in the order the events appear, print on its own line the highest reading on that stretch.

Example

2
6 6
3 1 4 1 5 9
a 0 5
a 1 3
b 2 7
a 1 3
b 5 -2
a 0 5
1 3
-5
a 0 0
b 0 10
a 0 0

9
4
7
7
-5
10

In the first testcase the readings start as $3,1,4,1,5,9$. The whole row peaks at $9$, and sensors $1$ to $3$ hold $1,4,1$, so their highest is $4$. Sensor $2$ is then recalibrated to $7$, which makes the same question answer $7$. Finally sensor $5$ drops to $-2$, the row becomes $3,1,7,1,5,-2$, and its highest is $7$.

Constraints

$1\le t\le 10$
$1\le n\le 10^5$
$1\le q\le 10^5$
$-10^9\le v_i,x\le 10^9$
$0\le l\le r\le n-1$ and $0\le i\le n-1$
The sum of $n$ over all testcases does not exceed $2\cdot 10^5$, and so does the sum of $q$