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
|