Module: Albero dei segmenti


Problem

2 /4


Albero dei segmenti

Theory Click to read/hide

Error

Problem

Corwin e Blaze si preparano a invadere Amber per rovesciare Erik. Per fare questo, hanno bisogno di formare un esercito. Nel mondo in cui si trovano, ci sono n insediamenti disposti in linea a causa del terreno. È noto che nel primo insediamento ci sono a1 guerrieri, nel secondo - a2, in i -th - ai, in n-th - an. 
A volte Corwin e Blaze scoprono che l'insediamento ai ha un numero di guerrieri diverso dal previsto. Corwin e Blaze ti chiedono m volte qual è il numero massimo di guerrieri che un insediamento può fornire al maggior numero di guerrieri. Aiutali a identificarlo.

Input
Nella prima riga, vengono inseriti i numeri n e m (1 <= n, m <= 100000) - il numero di liquidazioni e il numero di richieste .
La seconda riga contiene n numeri a1, a2 >, ..., an (1 <= ai <= 1000) - numero di guerrieri negli insediamenti.< /div >
Le seguenti righe m contengono i numeri t, l e r ( 1 <= l <= r <= n), (0 <= t <= 1) - se t è uguale a 0 allora l e r - confini della query. Altrimenti l è il numero della città e r è la nuova informazione.

Impressum
Sulla i-esima riga stampa la risposta alla i-esima query se ti=0, altrimenti print " ;-1".

 
Esempi
# Input Uscita
1
5 3
1 2 3 4 5
0 1 5
1 3 6
0 1 5
5
-1
6
 

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!