Kuten monilla asioilla maailmassa, tämän tehtävän otsikolla ei ole mitään merkitystä.

Annetaan suuntaamaton verkko, jossa on $n$ solmua ja $m$ kaarta. Kaaret on numeroitu järjestyksessä $1$:stä $m$:ään, ja jokaisella kaarella on paino $c_i$. Sinun tulee nyt vastata $q$ kyselyyn, joista jokainen on seuraavaa muotoa:

• Jos säilytetään vain ne kaaret, joiden indeksit ovat välillä $[l, r]$, mikä on kaikkien verkon siltakaarten painojen summa modulo $2^{64}$?

Sinun tulee vastata jokaiseen kyselyyn.

Haluat ehkä tietää sillan määritelmän: kaarta kutsutaan sillaksi jos ja vain jos sen poistaminen kasvattaa verkon yhtenäisten komponenttien lukumäärää.

Syöte

Ensimmäinen rivi sisältää luvut $n, m, q$ ($1 \le n \le 500$, $1 \le m, q \le 10^5$), jotka kuvaavat verkon solmujen, kaarten ja kyselyjen lukumäärää.

Seuraavat $m$ riviä sisältävät kukin kolme kokonaislukua $u, v, c$ ($1 \le u, v \le n$, $0 \le c < 2^{64}$), jotka kuvaavat verkon kaarta.

Seuraavat $q$ riviä sisältävät kukin kaksi positiivista kokonaislukua $l, r$ ($1 \le l \le r \le m$), jotka kuvaavat kyselyä.

On taattu, että verkko ei sisällä silmukoita, mutta se voi sisältää rinnakkaisia kaaria.

Tuloste

Tulosta jokaista kyselyä kohden yksi rivi, joka sisältää vastausta kuvaavan kokonaisluvun.

Esimerkki

Syöte 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

Tuloste 1

7
14
28
56
18
0