Wie so vieles auf der Welt hat auch der Titel dieses Problems keinerlei Bedeutung.

Gegeben ist ein ungerichteter Graph mit $n$ Knoten und $m$ Kanten. Die Kanten sind der Reihe nach von $1$ bis $m$ nummeriert, und jede Kante hat ein Gewicht $c_i$. Sie müssen nun $q$ Anfragen der folgenden Form beantworten:

• Wenn nur die Kanten mit Indizes in $[l, r]$ behalten werden, wie groß ist dann die Summe der Gewichte aller Brückenkanten im Graphen modulo $2^{64}$?

Sie müssen jede Anfrage beantworten.

Vielleicht möchten Sie die Definition einer Brücke wissen: Eine Kante wird genau dann als Brücke bezeichnet, wenn das Entfernen dieser Kante die Anzahl der Zusammenhangskomponenten im Graphen erhöht.

Eingabe

Die erste Zeile enthält $n, m, q$ ($1 \le n \le 500$, $1 \le m, q \le 10^5$), was die Anzahl der Knoten, Kanten und Anfragen im Graphen darstellt.

Die nächsten $m$ Zeilen enthalten jeweils drei ganze Zahlen $u, v, c$ ($1 \le u, v \le n$, $0 \le c < 2^{64}$), die eine Kante im Graphen darstellen.

Die nächsten $q$ Zeilen enthalten jeweils zwei positive ganze Zahlen $l, r$ ($1 \le l \le r \le m$), die eine Anfrage darstellen.

Es wird garantiert, dass der Graph keine Selbstschleifen enthält, er kann jedoch Mehrfachkanten enthalten.

Ausgabe

Geben Sie für jede Anfrage eine Zeile mit einer ganzen Zahl aus, die die Antwort darstellt.

Beispiel

Eingabe 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

Ausgabe 1

7
14
28
56
18
0