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

Poveste şi cerinţă...

Alexandra isi petrece vacanta de vara intr-o tabara, in care participantii au fost impartiti in echipe, iar ea a fost aleasa lider al uneia dintre ele. Echipele trec prin diferite probe in urma carora acumuleaza puncte, echipa cu cele mai multe puncte castigand trofeul taberei.
 
Pentru prima proba, fiecare echipa a primit o harta a taberei pe care sunt marcate $N$ locatii, numerotate de la $1$ la $N$ si o lista de sarcini numerotate de la $1$ la $S$, fiecare sarcina valorand un anumit numar de puncte. Sarcinile vor fi realizate tinand cont de instructiunile primite de la organizatori pe tot parcursul probei. Instructiunile sunt de $2$ tipuri:
 
1) Realizarea sarcinii $i$ permite realizarea sarcinii $j$ si invers (realizarea sarcinii $j$ permite realizarea sarcinii $i$).
2) La locatia i poate fi realizata sarcina $j$ dupa care pot fi realizate sarcinile permise de instructiunea $1$).
 
h2. Cerinta
 
Ajutati-o pe Alexandra ca pentru locatiile $i$ si $j$ date sa realizeze sarcina cu punctaj maxim pe care o poate indeplini plecand din orice locatie din intervalul [$i$, $j$].

h2. Date de intrare

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

Pe prima linie a fisierului de intrare $tabara.in$ se gasesc $3$ numere $N$, $S$ si $M$ reprezentand numarul de locatii, numarul de sarcini si, respectiv, numarul de instructiuni si cerinte. Pe a doua linie se afla $S$ numere semnificand punctajul sarcinilor in ordine, de la $1$ la $S$. Pe urmatoarele $M$ linii vor fi date instructiunile si cerintele. O linie va fi de forma:
 
1) $U 1 i j$ -> Realizarea sarcinii $i$ permite realizarea sarcinii $j$ si invers (realizarea sarcinii $j$ permite realizarea sarcinii $i$).
2) $U 2 i j$ -> La locatia $i$ poate fi realizata sarcina $j$ dupa care pot fi realizate sarcinile permise de instructiunea $1$).
3) $Q i j$ -> Sa se afiseze in fiesierul de iesire sarcina cu punctaj maxim pe care o poate realiza dintr-o locatie $k$, $i$ ≤ $k$ ≤ $j$.

h2. Date de ieşire

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

In fisierul de iesire $tabara.out$, pentru fiecare cerinta '$Q$' se va afisa numarul cerut pe cate o linie.

h2. Restricţii

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

* $1 ≤ N, S, M ≤ 100 000$
* Pentru $30%$ din teste $1 ≤ N, S, M ≤ 1 000$

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

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

| 2 4 6
  3 2 4 1
  U 1 2 4
  U 2 1 1
  U 2 2 2
  Q 1 2
  U 1 3 4
  Q 1 2
| 3
  4

|
h3. Explicaţie