Alveg eins og margt í heiminum hefur titill þessa verkefnis enga merkingu.

Gefið er óstefnt net með $n$ hnútum og $m$ leggjum, leggirnir eru númeraðir frá $1$ til $m$ í röð og hver leggur hefur þyngd $c_i$. Þú þarft nú að svara $q$ fyrirspurnum, hverri á eftirfarandi formi:

• Ef aðeins leggjum með vísa í $[l, r]$ er haldið eftir, hver er þá summa þyngda allra brúarleggja í netinu modulo $2^{64}$?

Þú þarft að svara hverri fyrirspurn.

Þú vilt kannski vita skilgreininguna á brú: leggur kallast brú ef og aðeins ef það að fjarlægja hann eykur fjölda samanhangandi þátta í netinu.

Inntak

Fyrsta línan inniheldur $n, m, q$ ($1 \le n \le 500$, $1 \le m, q \le 10^5$), sem tákna fjölda hnúta, leggja og fyrirspurna í netinu.

Næstu $m$ línur innihalda hver um sig þrjár heiltölur $u, v, c$ ($1 \le u, v \le n$, $0 \le c < 2^{64}$), sem tákna legg í netinu.

Næstu $q$ línur innihalda hver um sig tvær jákvæðar heiltölur $l, r$ ($1 \le l \le r \le m$), sem tákna fyrirspurn.

Tryggt er að netið innihaldi engar sjálfslykkjur, en það getur innihaldið margfalda leggi.

Úttak

Fyrir hverja fyrirspurn skal prenta eina línu sem inniheldur heiltölu sem táknar svarið.

Dæmi

Inntak 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

Úttak 1

7
14
28
56
18
0