Undeva, într-un ținut îndepărtat, își desfășoară activitatea o vestită companie, mai exact Mondial Computers SRL. Aceștia lucrează cu mulți clienți de renume, deci au nevoie de multă forță de muncă. Astfel, ei au o bază de date în care mențin informații despre angajații lor, dar, recent, echipa care se ocupa de această bază de date a dat dovadă de un randament scăzut, iar ca urmare a acestui fapt, manager-ul general a decis, fără a ține cont de consecințe, să îi concedieze, iar aceștia, de supărare, au șters înainte de a pleca din companie toate datele angajaților. Acum manager-ul are nevoie de ajutorul vostru(voluntar, desigur) pentru reorganizarea acestei baze de date până reușește să angajeze noi oameni.

Cerința

Compania dispune de N sedii în toată țara, numerotate de la 1 la N, iar când primesc o comandă aceasta poate fi plasată de către client la orice sediu dorește, iar comanda trebuie să poată ajunge prin căile de comunicație existente la orice alt sediu. Astfel, între cele N sedii există N - 1 căi de comunicație bidirecționale, astfel încât oricare 2 sedii diferite pot comunica între ele direct(printr-o singură cale) sau indirect(prin intermediul unui lanț de căi de comunicație). De asemenea, se consideră că sediul numerotat cu 1 este sediul principal al companiei. Astfel, putem considera că rețeaua sediilor este un arbore cu N noduri și rădăcina în nodul 1.

Compania are M angajați, numerotați de la 1 la M, iar fiecare dintre aceștia este caracterizat în mod special de un parametru F, care reprezintă forța sa de muncă și este singura informație de care mai dispune manager-ul despre angajații săi. Ca urmare a pierderii datelor, manager-ul mai decide și să angajeze provizoriu toți angajații la sediul central(nodul cu numărul 1 din arbore) pentru ca aceștia să aibă ce lucra. Pe parcursul următoarelor Q zile au loc evenimente de diferite tipuri, importante pentru organizarea companiei:

1.) Angajatul cu numărul de ordine k simte nevoia unei schimbări în cariera sa profesională și consideră un eventual transfer la alt sediu. În urma unei discuții cu manager-ul se stabilesc următoarele:
- angajatul poate pleca doar la un sediu ascendent sediului la care lucrează acum(adică nodul asociat noului sediu trebuie să se afle în subarborele cu rădăcina în nodul asociat sediului actual). De asemenea, acesta poate în final și să ajungă la decizia de a rămâne la sediul său actual.
- luând în considerare atât faptul că în prima zi de muncă într-un nou sediu s, un angajat primește o primă p[s], dar și acela că angajatul obosește dacă parcurge o distanță prea lungă până la noul sediu, s-a stabilit că sediul ales de angajat va fi cel care maximizează relația p[s] - d, unde d este distanța parcursă până la acel sediu. Dacă mai multe sedii maximizează această relație, se va alege cel cu numărul de ordine mai mic. De menționat că dacă angajatul vrea să rămână la sediul actual se consideră că d = 0.

2.) Manager-ul calculează suma primelor tuturor sediilor din subarborele nodului asociat sediului s și dacă aceasta este strict mai mică decât o valoare S stabilită de acesta, el hotărăște că sediile respective nu sunt atractive pentru angajați(se vrea ca angajații să fie cât mai dispersați în toate sediile companiei), deci toate sediile din subarborele dat care oferă prime cu o valoare mai mică de x unități monetare vor oferi de acum x unități monetare.

3.) Compania primește o comandă, iar manager-ul decide să procedeze astfel pentru realizarea acesteia: acesta alege prima dată un sediu s. Sediile implicate în realizarea comenzii vor fi toate sediile al căror nod corespondent în arborele caracteristic companiei se află în subarborele nodului reprezentativ pentru s(adică inclusiv acesta). În urma analizei de dificultate a comenzii, se hotărăște că este nevoie de cel puțin A angajați pentru a finaliza comanda la timp, iar manager-ul ar mai vrea și să aleagă o limită l, astfel încât orice angajat implicat în lucrare să aibă la momentul actual forța de muncă cel puțin l(pentru a implica angajați cât mai valoroși și, implicit, comanda să fie realizată cât mai calitativ), dar, în același timp să se poată alege cel puțin A angajați pentru comandă. Astfel, manager-ul vrea să afle care este valoarea maximă ce poate fi aleasă pentru l. Dacă nu se pot alege cel puțin A angajați orice valoare am alege pentru limita l, atunci comanda nu poate fi realizată.

Misiunea voastră este să realizați un program care poate procesa toate aceste evenimente. Succes!

Date de intrare

Pe prima linie se va citi de la tastatură un număr natural N, având semnificația din enunț. A doua linie conține N numere naturale, al i-lea dintre ele fiind valoarea lui p[i], acestea având, de asemenea, semnificația din enunț. Următoarele N - 1 linii vor conține câte 2 numere naturale u v semnificând faptul că există o cale de comunicație bidirecțională între sediile u și v.

Linia N + 2 conține numărul natural M cu semnificația din enunț, iar următoarea linie conține M numere, al i-lea dintre ele semnificând valoarea lui F[i] – forța de muncă a celui de-al i-lea angajat.

Linia N + 4 conține numărul natural Q cu semnificația din enunț, iar fiecare din următoarele Q linii conține câte un eveniment având următoarea structură:
- 1 k – eveniment de tipul 1;
- 2 s S x – eveniment de tipul 2;
- 3 s A – eveniment de tipul 3.
Variabilele ce apar în structura evenimentelor au semnificațiile din enunț.

Date de ieșire

Programul va afișa pe ecran pe câte o linie rezultatele evenimentelor de tip 3 în ordinea în care acestea apar în input. Dacă o comandă nu poate fi realizată, rezultatul asociat evenimentului de tipul 3 pentru acea comandă este -1.

Restricții și precizări

• 1 ≤ N, M, Q ≤ 100.000
• 1 ≤ u, v ≤ N
• 1 ≤ p[i], F[i], x ≤ 1.000.000.000
• 1 ≤ S ≤ 1.000.000.000.000
• 1 ≤ k, A ≤ M

Exemplu:

Intrare

14
10 5 3 4 6 7 9 14 20 13 16 8 5 18 
1 2
1 3
1 4
2 5
3 8
4 10
4 11
5 6
5 7
8 9
11 12
11 13
11 14
10
10 11 6 5 7 8 9 12 20 13
10
1 2 
1 10
1 5
3 9 2
2 11 100 30
1 8
1 7
3 12 1
3 11 3 
3 1 7

Ieșire

11
-1
-1
8

Explicație

Arborele asociat exemplului arată în felul următor(valorile scrise lângă noduri corespund valorilor inițiale ale primelor fiecăruia):

Inițial toți angajații lucrează la sediul principal.

În urma primelor 3 evenimente, angajații cu numerele de ordine 2, 10, respectiv 5 se vor muta la sediul cu numărul 9.

Angajații care lucrează la sediul 9(acesta fiind și singurul sediu din subarborele său) au forțele de muncă 7, 11, respectiv 13. Pentru a putea alege 2 angajați limita maximă ce poate fi aleasă este 11(angajații aleși sunt cei cu numerele de ordine 2 și 10).

În a 5-a zi manager-ul observă că sediile din subarborele nodului 11 nu sunt destul de atractive pentru angajați(suma lor fiind 47, iar target-ul ales de acesta fiind 100), deci le maximizează primele cu 30 de unități monetare.

În zilele 6 și 7 angajații cu numerele de ordine 8 și 7 se vor muta la sediul cu numărul 11.

În ziua 8 se vrea alegerea unui angajat din sediul 12 pentru a se efectua o comandă, dar sediul 12 nu are angajați, deci comanda nu poate fi realizată, iar rezultatul este -1.

În ziua 9 se vrea alegerea a 3 angajați astfel din sediile aflate în subarborele nodului 11, dar în acest subarbore există în total doar 2 angajați, deci analog cu situația din ziua precedentă, comanda nu poate fi realizată, iar rezultatul este -1.

În ultima zi se aleg 7 angajați din toate sediile pentru a maximiza limita. Cum există mai mult de 7 angajați în total, comanda poate fi realizată, iar limita aleasă este 8.