Module: Pokok segmen


Problem

2 /4


Pokok segmen

Theory Click to read/hide

Error

Problem

Corwin dan Blaze bersedia untuk menyerang Amber untuk menggulingkan Erik. Untuk melakukan ini, mereka perlu mengumpulkan tentera. Di dunia tempat mereka berada, terdapat n penempatan yang disusun dalam satu barisan kerana rupa bumi. Diketahui bahawa di penempatan pertama terdapat a1 pahlawan, dalam yang kedua - a2, dalam i -th - ai, dalam n-th - an. 
Kadangkala Corwin dan Blaze mengetahui bahawa penempatan ai mempunyai bilangan pahlawan yang berbeza daripada yang dijangkakan. Corwin dan Blaze bertanya kepada anda m kali berapa bilangan maksimum pahlawan yang boleh dibekalkan oleh penempatan paling ramai pahlawan. Bantu mereka mengenal pastinya.

Input
Dalam baris pertama, nombor n dan m (1 <= n, m <= 100000) adalah input - bilangan penyelesaian dan bilangan permintaan .
Baris kedua mengandungi n nombor a1, a2 >, ..., an (1 <= ai <= 1000) - bilangan pahlawan di penempatan.< /div >
Barisan m berikut mengandungi nombor t, l dan r ( 1 <= l <= r <= n), (0 <= t <= 1) - jika t sama dengan 0 maka l dan r - sempadan pertanyaan. Jika tidak l ialah nombor bandar dan r adalah maklumat baharu.

Cetakan
Pada baris i-cetak jawapan kepada pertanyaan i-jika ti=0, jika tidak cetak " ;-1".

 
Contoh
 

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!

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