h2. Date de ieşire

În fişierul de ieşire $infinitywar.out$ ...

Fişierul de ieşire $infinitywar.out$ trebuie să conţină $Q$ linii. Fiecare linie trebuie să conţină un singur număr, raspunul pentru întrebarea corespunzătoare.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ N ≤ 50.000$
* $1 ≤ P ≤ 10.000$
* $1 ≤ Q ≤ 100.000$
* $K{~1~} + K{~2~} + ... + K{~N~} ≤ 300.000$
* $1 ≤ x ≤ y ≤ N$ pentru fiecare întrebare.

h2. Exemplu
table(example). |_. infinitywar.in |_. infinitywar.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|4 3
2 1 2
3 1 3 97
2 1 341
5 4 2 981 341 97
1 3
2 4
1 4
|5
4
4

|

h3. Explicaţie
 
...
 

== include(page="template/taskfooter" task_id="infinitywar") ==