Problem

2 /4


شجرة القطعة

Theory Click to read/hide

Error

Problem

يستعد كوروين وبليز لغزو العنبر للإطاحة بإريك. للقيام بذلك ، يحتاجون إلى تكوين جيش. في العالم الذي توجد فيه ، توجد مستوطنات n مرتبة في خط بسبب التضاريس. من المعروف أنه في التسوية الأولى يوجد a 1 محاربين ، في الثانية - a 2 ، في i -th - a i ، في n -th - a n . & nbsp؛
في بعض الأحيان يكتشف كوروين وبليز أن التسوية a i بها عدد من المحاربين مختلف عن المتوقع. يسألك Corwin و Blaze عن m & nbsp؛ مرات ما هو الحد الأقصى لعدد المحاربين الذين يمكن أن توفرهم التسوية لمعظم المحاربين. ساعدهم في التعرف عليه.

إدخال
في السطر الأول ، يتم إدخال الأرقام n & nbsp؛ و m & nbsp؛ (1 & lt؛ = n، m & lt؛ = 100000) - عدد التسويات وعدد الطلبات.
يحتوي السطر الثاني على n & nbsp؛ أرقام a 1 ، a 2 > ، ... ، a n (1 & lt؛ = a i & lt؛ = 1000) - عدد المحاربين في المستوطنات. < / div>
تحتوي الأسطر التالية m & nbsp؛ على الأرقام t و l & nbsp؛ و r & nbsp؛ ( 1 & lt؛ = l & lt؛ = r & lt؛ = n)، (0 & lt؛ = t ​​& lt؛ = 1) - إذا كان t & nbsp؛ يساوي 0 إذًا l & nbsp؛ و r & nbsp؛ - حدود الاستعلام. بخلاف ذلك ، يكون & nbsp؛ l & nbsp؛ رقم المدينة و r & nbsp؛ معلومات جديدة.

بصمة
في السطر رقم i -th ، اطبع الإجابة على الاستعلام رقم i إذا كان t i = 0 ، وإلا طباعة & quot؛ -1 & quot ؛.

نبسب ؛
أمثلة <الجسم>
# إدخال الإخراج
1
5 3
1 2 3 4 5
0 1 5
1 3 6
0 1 5
5
-1
6
& nbsp؛

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!