Олимпиадный тренинг

Задача 23581. segment tree


Задача

Темы:
Corwin and Blaze prepare to invade Amber to overthrow Erik. To do this, they need to raise an army. In the world where they are located, there are n settlements arranged in a line due to the terrain. It is known that in the first settlement there are a1 warriors, in the second - a2, in i -th - ai, in n-th - an
Sometimes Corwin and Blaze find out that the ai settlement has a different number of warriors than expected. Corwin and Blaze ask you m times what is the maximum number of warriors a settlement can supply the most warriors. Help them identify it.

Input
In the first line, the numbers n and m (1 <= n, m <= 100000) are input - the number of settlements and the number of requests .
The second line contains n numbers a1, a2 >, ..., an (1 <= ai <= 1000) - number of warriors in settlements.
The following m lines contain the numbers t, l and r (1 <= l <= r <= n), (0 <= t <= 1) - if t is equal to 0 then l and r - query boundaries. Otherwise l is the city number and r is new information.

Imprint
On the i-th line print the answer to the i-th query if ti=0, otherwise print " ;-1".

 
Examples
# Input Output
1
5 3
1 2 3 4 5
0 1 5
1 3 6
0 1 5
5
-1
6