Maksimum promenljivog segmenta

Meteorološka služba drži $n$ senzora poređanih duž planinskog puta, označenih brojevima od $0$ do $n-1$, i svaki senzor javlja po jednu temperaturu.

Tokom dana se, iznova i iznova, dešavaju dve stvari:

• prognozer pita koja je najviša temperatura koju javljaju senzori na nekoj deonici puta,
• neki senzor se prekalibriše, pa se njegovo očitavanje zameni novim.

Napiši program koji odgovara na svako pitanje, koristeći očitavanja onakva kakva su u tom trenutku.

Ulaz

U prvoj liniji ulaza je jedan ceo broj $t$ - broj test primera.
U prvoj liniji svakog test primera su dva cela broja $n$ i $q$ - broj senzora i broj događaja.
U drugoj liniji je $n$ celih brojeva $v_0,v_1,\dots ,v_{n-1}$ - očitavanja sa kojima senzori kreću.
U svakoj od sledećih $q$ linija je po jedan događaj, u jednom od dva oblika:

• a l r - ispiši najviše očitavanje među senzorima $l,l+1,\dots ,r$;
• b i x - senzor $i$ je prekalibrisan, njegovo očitavanje postaje $x$.

Senzori su numerisani od $0$, pa su $l$, $r$ i $i$ svi između $0$ i $n-1$.

Izlaz

Za svaki događaj tipa a, redom kojim se događaji javljaju, ispiši u posebnoj liniji najviše očitavanje na toj deonici.

Primer

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

U prvom test primeru očitavanja kreću kao $3,1,4,1,5,9$. Ceo niz se penje do $9$, a senzori od $1$ do $3$ drže $1,4,1$, pa je njihov najviši $4$. Senzor $2$ se zatim prekalibriše na $7$, čime isto pitanje daje odgovor $7$. Na kraju senzor $5$ pada na $-2$, niz postaje $3,1,7,1,5,-2$, a njegov najviši je $7$.

Ograničenja

$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$ i $0\le i\le n-1$
Zbir $n$ preko svih test primera ne prelazi $2\cdot 10^5$, kao ni zbir $q$