h2. Restricţii

* Fie $S$ = suma tuturor $K$-urilor de la intrare.
* Costul oricarei muchii este
* Raspunsul pentru fiecare query este < %{color:black} 2^63^%sub $1 000 000$

Fie $S$ = suma tuturor $K$-urilor de la intrare.
Costul oricarei muchii este sub $1 000 000$

table(restrictii). |_. # |_. Punctaj |_. Restricţii |
| $1$ | $8$ | $1 ≤ N, M, S ≤ 1 000$ |

| $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$ |

Raspunsul pentru fiecare query este <

h2. Exemplu