== include(page="template/taskheader" task_id="mit") ==

Poveste şi cerinţă...

Dumitiran, profesor la concurenta Universitatii MIT (Multa Informatica pe Tava), a creat un sistem ingenios de notare a studentilor la final de semestru. Acesta stie notele fiecarui student de la examenul de SD (acestia fiind pe Lista Sa indexati de la 1) , dar doreste sa dea bonus mai multora dintre ei, conform regulamentului de la inceputul semestrului. Acesta a uitat insa ce studenti meritau acel bonus, insa are vagi informatii. Dumitiran poate aplica 2 tipuri de operatii:
 
* de tipul 1: vrea sa stie care este nota maxima a elevilor din intervalul A - B;
* de tipul 2: stie ca are cativa studenti vrednici in intervalul A - B, insa nestiind exact care, decide sa dea un bonus de X puncte tuturor elevilor din acest interval

h2. Date de intrare

Fişierul de intrare $mit.in$ ...

Fişierul de intrare $mit.in$ va contine pe prima linie 2 numere N si T, reprezentand numarul de elevi de pe lista lui Dumitiran, respectiv numarul de operatii aplicate de acesta. Pe linia a 2-a se vor afla N numere reprezentand notele initiale ale studentilor. Pe urmatoarele T linii se vor afla informatiile despre operatii: 1 A B (daca este operatie de tip 1) sau 2 A B X daca este operatie de tip 2).

h2. Date de ieşire

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

În fişierul de ieşire $mit.out$ se vor afla pe cate o linie raspunsurile la operatiile de tip 1.

h2. Restricţii

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

* $1 ≤ N, T ≤ 100.000$
* Pentru 40 puncte, $1 ≤ N, T ≤ 1.000$ (Testele 1-4)
* Pentru 20 puncte, vor exista maxim 50 de operatii de tip 2 (acestea fiind primele in input), iar toate restul fiind de tip 2 (la finalul inputului), (Testele 5-6)
* Notele initiale sunt numere naturale pozitive <= 10.000
* $1 &le; X &le; 10.000$ pentru oricare dintre teste

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

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

| 7 4
1 2 0 4 5 1 2
1 2 5
2 3 6 3
2 1 5 1
1 1 4
| 5
8

|

h3. Explicaţie
 
...
 

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