Arbore

Se dă un arbore cu $N$ noduri, numerotate de la $1$ la $N$ . Fiecare muchie din arbore are un cost număr natural nenul asociat. O operație constă în a alege o muchie cu costul strict pozitiv și a-i scădea costul cu $1$.

Pentru un nod $v$ din arbore și un număr natural $k$, se notează cu $f(v, k)$ suma minimă a costurilor drumurilor de la nodul $v$ la restul nodurilor din arbore care se poate obține aplicând în mod optim cel mult $k$ operații de tipul descris anterior.

Cerință

Se dau $Q$ interogări de forma $(v, k_1, k_2)$, unde $v$ este un nod din arbore, iar $k_1$ și $k_2$ sunt numere naturale astfel încât $k_1 ≤ k_2$. Pentru fiecare interogare să se calculeze $\displaystyle \sum_{k=k_1}^{k_2} f (v, k)$, adică suma valorilor $f (v, k)$ pentru $k_1 ≤ k ≤ k_2$, modulo $10^9 + 7$.

Date de intrare

Prima linie a fişierului de intrare arbore.in conţine numărul $N$ , reprezentând numărul de noduri din arbore.

Pe următoarele $N − 1$ linii se află câte $3$ numere $u \ v \ w$, reprezentând o muchie din arbore între nodurile $u$ și $v$, care are costul $w$.

Următoarea linie conține un singur număr $Q$, reprezentând numărul de interogări, iar pe următoarele $Q$ linii se află câte trei numere $v \ k_1 \ k_2$, cu semnificația din enunț.

Date de ieșire

Fișierul de ieșire arbore.out trebuie să conțină $Q$ linii, fiecare coținând câte un număr natural care reprezintă răspunsul pentru fiecare interogare dată, în ordinea în care acestea sunt date în fișierul de intrare.

Restricții și precizări

• $1 \leq N \leq 200 \ 000$
• $1 \leq Q \leq 400 \ 000$
• $1 \leq w \leq 10^8$
• $0 \leq k_1 \leq k_2 \leq 10^{14}$

Exemple

arbore.in

5
1 2 3
2 3 4
2 5 6
1 4 2
4
1 4 5
2 1 1
5 20 22
4 0 0

arbore.out

21
16
0
27

Explicație

Arborele are $N = 5$ noduri si este ilustrat în Figura 1 împreună cu costurile asociate muchiilor sale. Se dau $Q = 4$ interogări, după cum urmează.

• Prima interogare: Pentru $k = 4$ se poate aplica operația descrisă în enunț muchiei $1−2$ de $3$ ori, respectiv muchiei $1−4$ o dată, deci $f(1, 4) = 11$. Pentru $k = 5$ se poate aplica operația descrisă în enunț muchiei $1−2$ de $3$ ori, muchiei $2−3$ o dată, respectiv muchiei $2−5$ o dată, deci $f(1, 5) = 10$. Astfel, răspunsul este $f(1, 4) + f(1, 5) = 11 + 10 = 21$.
• A doua interogare: Se poate scădea costul muchiei $1−2$ o dată, deci răspunsul este $f(1, 1) = 16$.
• A treia interogare: Se obervă că pentru oricare $20 ≤ k ≤ 22$, costurile tuturor muchiile din arbore pot fi scăzute până ajung la valoarea $0$ (mai mult de atât nu este permis din definiția operației date), deci rezultatul este $0$.
• A patra interogare: $k_1 = k_2 = 0$, deci nu avem la dispoziție nicio operație care să scadă costul muchiilor. Astfel, răspunsul este dat de suma costurilor drumurilor de la nodul $4$ la restul nodurilor din arbore, care este $2 + 5 + 9 + 11 = 27$.