Precis som med mycket annat i världen har titeln på detta problem ingen betydelse.

Givet en oriktad graf med $n$ hörn och $m$ kanter, där kanterna är numrerade från $1$ till $m$ i ordning och varje kant har en vikt $c_i$. Du ska nu besvara $q$ frågor, var och en på följande form:

• Om endast kanterna med index i $[l, r]$ behålls, vad är summan av vikterna för alla brokanter (bridges) i grafen modulo $2^{64}$?

Du måste besvara varje fråga.

Du kanske vill veta definitionen av en bro: en kant kallas en bro om och endast om borttagandet av den ökar antalet sammanhängande komponenter i grafen.

Indata

Den första raden innehåller $n, m, q$ ($1 \le n \le 500$, $1 \le m, q \le 10^5$), som representerar antalet hörn, kanter och frågor i grafen.

De följande $m$ raderna innehåller var och en tre heltal $u, v, c$ ($1 \le u, v \le n$, $0 \le c < 2^{64}$), som representerar en kant i grafen.

De följande $q$ raderna innehåller var och en två positiva heltal $l, r$ ($1 \le l \le r \le m$), som representerar en fråga.

Det garanteras att grafen inte innehåller några öglor, men den kan innehålla multipelkanter.

Utdata

För varje fråga, skriv ut en rad som innehåller ett heltal som representerar svaret.

Exempel

Indata 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