Module: Arborescence des segments


Problem

2 /4


Arborescence des segments

Theory Click to read/hide

Error

Problem

Corwin et Blaze se préparent à envahir Amber pour renverser Erik. Pour ce faire, ils doivent lever une armée. Dans le monde où ils se trouvent, il y a n colonies disposées en ligne en raison du terrain. On sait que dans la première colonie il y a des guerriers a1, dans la seconde - a2, dans i -ème - ai, en n-ème - an. 
Parfois, Corwin et Blaze découvrent que la colonie ai a un nombre de guerriers différent de celui prévu. Corwin et Blaze vous demandent m fois quel est le nombre maximum de guerriers qu'une colonie peut fournir le plus de guerriers. Aidez-les à l'identifier.

Entrée
Sur la première ligne, les nombres n et m (1 <= n, m <= 100000) sont entrés - le nombre de règlements et le nombre de demandes .
La deuxième ligne contient n nombres a1, a2 >, ..., an (1 <= ai <= 1000) - nombre de guerriers dans les colonies.< /div >
Les lignes m suivantes contiennent les nombres t, l et r ( 1 <= l <= r <= n), (0 <= t <= 1) - si t est égal à 0 alors l et r - limites de la requête. Sinonl est le numéro de la ville et r est une nouvelle information.

Mentions légales
Sur la i-ème ligne imprimer la réponse à la i-ème requête si ti=0, sinon imprimer "-1".

 
Exemples
5 3
1 2 3 4 5
0 1 5
1 3 6
0 1 5
5
-1
6
# Entrée Sortie
1
 

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!