Podobnie jak wiele rzeczy na świecie, tytuł tego zadania nie ma żadnego znaczenia.

Dany jest graf nieskierowany o $n$ wierzchołkach i $m$ krawędziach; krawędzie są ponumerowane kolejno od $1$ do $m$, a każda krawędź ma wagę $c_i$. Musisz teraz odpowiedzieć na $q$ zapytań, z których każde ma następującą postać:

• Jeśli pozostawimy tylko krawędzie o indeksach z przedziału $[l, r]$, to jaka jest suma wag wszystkich krawędzi będących mostami w tym grafie modulo $2^{64}$?

Musisz odpowiedzieć na każde zapytanie.

Być może chcesz poznać definicję mostu: krawędź nazywamy mostem wtedy i tylko wtedy, gdy jej usunięcie zwiększa liczbę spójnych składowych w grafie.

Wejście

Pierwszy wiersz zawiera liczby $n, m, q$ ($1 \le n \le 500$, $1 \le m, q \le 10^5$), oznaczające liczbę wierzchołków, krawędzi oraz zapytań w grafie.

Kolejne $m$ wierszy zawiera po trzy liczby całkowite $u, v, c$ ($1 \le u, v \le n$, $0 \le c < 2^{64}$), oznaczające krawędź w grafie.

Kolejne $q$ wierszy zawiera po dwie dodatnie liczby całkowite $l, r$ ($1 \le l \le r \le m$), oznaczające zapytanie.

Gwarantuje się, że graf nie zawiera pętli własnych, ale może zawierać krawędzie wielokrotne.

Wyjście

Dla każdego zapytania wypisz jeden wiersz zawierający liczbę całkowitą oznaczającą odpowiedź.

Przykład

Wejście 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

Wyjście 1

7
14
28
56
18
0