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

== include(page="template/detailed-feedback" task_id="tabara2") ==
 

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$).

2) La locatia $i$ poate fi realizata sarcina $j$ (dupa care pot fi realizate sarcinile permise de instructiunea $1$).

h2. Cerinta

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$).

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

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

* Se garanteaza ca o sarcina poate fi indeplinita numai dintr-o locatie.

* **Atentie!** Se garanteaza ca o sarcina poate fi indeplinita numai dintr-o locatie (direct sau indirect).

* Punctajul unei sarcini este ≤ $1 000 000 000$.
h2. Exemplu

4266