LAN Party

Calea succesului. Toate drumurile duc spre Roma

Într-o seară, lui Raul i-a venit o idee inedită: să organizeze un LAN party de CS2 împreună cu prietenii săi.

Cum știm că "Toate drumurile duc spre Roma", putem spune că fiecare oraș din Europa formează un arbore, Roma fiind rădăcină arborelui. Fiecare dintre cei $F$ prieteni ai lui Raul se află într-un oraș diferit din Europa. Pentru a economisi bani, fiecare prieten va călători gratuit folosind metoda Ia-mă nene.

Totuși, există o problemă. De fiecare dată când ajunge într-un nou oraș, fiecare prieten i se face foame. Cum nenea nu intră în oraș, acesta îl lasă pe prieten la intrarea orașului, iar prietenul trebuie să ia un taxi pentru a ajunge la un restaurant. După ce a mâncat o să ia un alt taxi până în afara orașului. Dacă doi sau mai mulți prieteni se întâlnesc la intrarea unui oraș, aceștia pot folosi același taxi și pot mânca din acelaș preparat la restaurant. Din păcate, nu este permis să strecoare mâncarea din restaurant pentru a o lua pe drum :(((((.

Pentru fiecare oraș se cunoaște costul taxiului și al preparatului din restaurant. Un prieten poate alege să aștepte în afara orașului pentru a se întâlni cu alți prieteni care au drum prin același oraș sau poate să meargă singur cu taxiul și să mânânce singur.

Cerință

Din păcate, nu toți prietenii pot veni la acest LAN party, așa că vi se oferă $Q$ situații. Pentru fiecare situație, trebuie să aflați costul minim pe care îl vor cheltui prietenii din intervalul $[l, r]$ pentru a se întâlni.

Date de intrare

Pe prima linie se găsesc trei numere: $N, Q$ și $F$. $N$ fiind numărul de orașe din Europa, $Q$ numărul de întrebări, iar $F$ numărul de prieteni.
Pe a doua linie se găsesc costurile specifice pentru cele $N$ orașe, de la $1$ la $N$.
Pe a treia linie se găsește șirul $t$, ($t_i$, $i=\overline{2,N}$), reprezentând orașul în care poți ajunge în mod direct din orașul $i$ și viceversa.
Pe a patra linie se găsesc orașele în care se află cei $F$ prieteni a lui Raul.
Pe următoarele $Q$ linii se găsesc două numere, $l$ și $r$, reprezentând intervalul de prieteni care se vor întâlni cu Raul.

Date de ieșire

Pe $Q$ linii se vor afișa costul minim aruncat de prieteni lui Raul pentru a se întâlni. Cum costul poate să fie foarte mare, se cere să se afișeze modulo $10^9+7$.

Restricții și precizări

• $1 \leq Q \leq 1 \ 000 \ 000$
• $1 \leq N, F \leq 400 \ 000$
• Numărul de prieteni din cele $Q$ situații $\leq 1 \ 000 \ 000$
• Costurile specifice fiecărui oraș $\leq 2^{63}-1$
• LAN party-ul poate fi organizat în orice oraș, cu condiția ca cheltuielile prietenilor să fie minime.
• Dacă în acelaș restaurant, doi sau mai mulți prieteni ajung în acelaș moment, aceștia vor mânca doar dintr-un preparat. Cantitatea este infinită.
• Raul poate ajunge gratuit în orice oraș.

Exemplul 1

stdin

12 6 6
1 1 1 1 1 1 1 1 1 1 1 1
1 1 2 2 2 3 5 5 6 9 9
4 8 9 10 12 7
1 2
1 3
1 4
3 4
1 6
4 5

stdout

4
5
7
5
11
6

Explicație

Crede-mă pe cuvânt, răspunsurile sunt corecte.