Akkurat som mye annet i verden, har tittelen på denne oppgaven ingen betydning.

Gitt en urettet graf med $n$ hjørner og $m$ kanter, der kantene er nummerert fra $1$ til $m$ i rekkefølge, og hver kant har en vekt $c_i$. Du må nå svare på $q$ spørringer, hver på følgende form:

• Hvis bare kantene med indekser i $[l, r]$ beholdes, hva er summen av vektene til alle brokanter i grafen modulo $2^{64}$?

Du må svare på hver spørring.

Du vil kanskje vite definisjonen av en bro: en kant kalles en bro hvis og bare hvis det å fjerne den øker antallet sammenhengende komponenter i grafen.

Inndata

Den første linjen inneholder $n, m, q$ ($1 \le n \le 500$, $1 \le m, q \le 10^5$), som representerer antallet hjørner, kanter og spørringer i grafen.

De neste $m$ linjene inneholder hver tre heltall $u, v, c$ ($1 \le u, v \le n$, $0 \le c < 2^{64}$), som representerer en kant i grafen.

De neste $q$ linjene inneholder hver to positive heltall $l, r$ ($1 \le l \le r \le m$), som representerer en spørring.

Det er garantert at grafen ikke inneholder noen løkker, men den kan inneholde parallelle kanter.

Utdata

For hver spørring skal du skrive ut én linje som inneholder et heltall som representerer svaret.

Eksempel

Inndata 1

5 6 6
1 2 1
2 3 2
2 4 4
2 5 8
1 3 16
4 5 32
1 3
2 4
3 5
4 6
2 6
1 6

Utdata 1

7
14
28
56
18
0