* Fie $S$ = suma tuturor $K$-urilor de la intrare.
* Costul fiecarei muchii este mai mic sau egal decat $1 000 000$

* Raspunsul se incadreaza intr-un tip de date cu 64 de biti cu semn
* Pentru orice subtask, daca nu este precizat, $K ≥ 2$, si implicit $2 * Q ≤ S$
 

* Raspunsul pentru fiecare query este mai mic decat $2^63$

table(restrictii). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $8$ | $1 ≤ N, M, S ≤ 1 000$ |
| $2$ | $23$ | $1 ≤ N ≤ 100 000, 1 ≤ S, M ≤ 200 000, K = 2$|

| $3$ | $19$ | $1 ≤ N ≤ 100 000, M = N-1, 1 ≤ S ≤ 200 000, Graful este un lant$|
| $4$ | $16$ | $1 ≤ N ≤ 100 000, 1 ≤ S, M ≤ 200 000$, $1 ≤ Q ≤ 200$ |

| $3$ | $19$ | $1 ≤ N ≤ 100 000, 1 ≤ S, M ≤ 200 000, Graful este un lant$|
| $4$ | $16$ | $1 ≤ N ≤ 100 000, 1 ≤ S, M ≤ 200 000$, $1 ≤ Q ≤ 100$ |

| $5$ | $34$ | $1 ≤ N, S ≤ 500 000, 1 ≤ M ≤ 1 000 000$ |