Proprio come molte cose al mondo, il titolo di questo problema non ha alcun significato.

Dato un grafo non orientato con $n$ vertici e $m$ archi, gli archi sono numerati da $1$ a $m$ in ordine, e ciascun arco ha un peso $c_i$. Ora devi rispondere a $q$ query, ciascuna nella forma seguente:

• Se vengono mantenuti solo gli archi con indici in $[l, r]$, qual è la somma dei pesi di tutti gli archi ponte nel grafo modulo $2^{64}$?

Devi rispondere a ciascuna query.

Potresti voler conoscere la definizione di ponte: un arco è chiamato ponte se e solo se la sua rimozione aumenta il numero di componenti connesse nel grafo.

Input

La prima riga contiene $n, m, q$ ($1 \le n \le 500$, $1 \le m, q \le 10^5$), che rappresentano il numero di vertici, archi e query nel grafo.

Le successive $m$ righe contengono ciascuna tre interi $u, v, c$ ($1 \le u, v \le n$, $0 \le c < 2^{64}$), che rappresentano un arco nel grafo.

Le successive $q$ righe contengono ciascuna due interi positivi $l, r$ ($1 \le l \le r \le m$), che rappresentano una query.

È garantito che il grafo non contenga cappi, ma può contenere archi multipli.

Output

Per ogni query, stampa una riga contenente un intero che rappresenta la risposta.

Esempio

Input 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

Output 1

7
14
28
56
18
0