Corsa

Te-ai decis să ieși la o plimbare cu Opelozaurul pe un traseu care conține la fiecare kilometru un indicator cu numerele naturale din intervalul $[1, n]$, în ordine crescătoare. Îți începi traseul în dreptul indicatorului cu numărul $1$ și îl termini la indicatorul cu numărul $n$.

În mod normal, reușești să parcurgi orice kilometru cu mașina în $100$ de secunde, dar, înainte să începi cursa, drumul a fost afectat de precipitații.

Prima data a fost afectat de ninsori, fiecare ninsoare fiind descrisă printr-un triplet, $L, R$ și $k$, care arată că ninsoarea a afectat drumul în intervalul delimitat de indicatoarele $L$ și $R$, iar acum, în acel interval, numărul de secunde în care reușești să parcurgi un kilometru crește cu $k$, indiferent de valoarea lui precedentă.

După ninsori, drumul este afectat de ploi, care sunt descrise și ele prin triplete $L, R, k$ și limitează timpul în care mașina poate să parcurgă un kilometru în intervalul delimitat de indicatoarele $L$ și $R$ la $k$ secunde.

Se dau $q$ numere întregi $p$ din intervalul $[1, n]$, iar pentru fiecare trebuie să determini numărul de secunde necesare să ajungi în dreptul panoului $p$.

Date de intrare

Prima linie va conține numărul natural $n$. Pe cea de a doua linie se citesc numerele $s, r, q$ - numărul de ninsori, ploi, respectiv numărul de întrebări. Următoarele $s$ linii vor conține câte un triplet, reprezentând ninsorile, apoi, următoarele $r$ linii vor conține câte un triplet reprezentând ploile, iar ultimele $q$ linii vor conține numerele naturale $p$.

Date de ieșire

Se vor afișa $p$ linii, fiecare linie conținând răspunsul la o întrebare.

Restricții și precizări

• $L < R$
• $2 \leq N \leq 10^{10}$
• $s, r, q, k \leq 10^5$

Exemplul 1

corsa.in

10
1 2 2
3 6 15
5 8 110
7 10 107
5
9

corsa.out

430
872

Explicație

După ninsoare, vitezele pentru fiecare segment sunt:
$100 \ 100 \ 115 \ 115 \ 115 \ 100 \ 100 \ 100 \ 100$
După prima ploaie, vitezele pentru fiecare segment sunt:
$100 \ 100 \ 115 \ 115 \ 115 \ 110 \ 110 \ 100 \ 100$
Apoi, după ultima ploaie, vitezele pe segmente sunt:
$100 \ 100 \ 115 \ 115 \ 115 \ 110 \ 110 \ 107 \ 107$
Primul număr reprezintă viteza pe segmentul $1-2$, al doilea număr reprezintă viteza pe segmentul $2-3$ și așa mai departe.