Comme beaucoup de choses dans le monde, le titre de ce problème n'a aucun sens.

Étant donné un graphe non orienté avec $n$ sommets et $m$ arêtes, les arêtes sont numérotées de $1$ à $m$ dans l'ordre, et chaque arête a un poids $c_i$. Vous devez maintenant répondre à $q$ requêtes, chacune sous la forme suivante :

• Si seules les arêtes dont les indices sont dans $[l, r]$ sont conservées, quelle est la somme des poids de toutes les arêtes qui sont des ponts dans le graphe modulo $2^{64}$ ?

Vous devez répondre à chaque requête.

Vous voudrez peut-être connaître la définition d'un pont : une arête est appelée un pont si et seulement si sa suppression augmente le nombre de composantes connexes dans le graphe.

Entrée

La première ligne contient $n, m, q$ ($1 \le n \le 500$, $1 \le m, q \le 10^5$), représentant le nombre de sommets, d'arêtes et de requêtes dans le graphe.

Les $m$ lignes suivantes contiennent chacune trois entiers $u, v, c$ ($1 \le u, v \le n$, $0 \le c < 2^{64}$), représentant une arête dans le graphe.

Les $q$ lignes suivantes contiennent chacune deux entiers strictement positifs $l, r$ ($1 \le l \le r \le m$), représentant une requête.

Il est garanti que le graphe ne contient pas de boucles, mais il peut contenir des arêtes multiples.

Sortie

Pour chaque requête, affichez une ligne contenant un entier représentant la réponse.

Exemple

Entrée 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

Sortie 1

7
14
28
56
18
0