Just like many things in the world, the title of this problem has no meaning.

Given an undirected graph with $n$ vertices and $m$ edges, the edges are numbered from $1$ to $m$ in order, and each edge has a weight $c_i$. You now need to answer $q$ queries, each in the following form:

• If only the edges with indices in $[l, r]$ are kept, what is the sum of the weights of all bridge edges in the graph modulo $2^{64}$?

You need to answer each query.

You may want to know the definition of a bridge: an edge is called a bridge if and only if removing it increases the number of connected components in the graph.

Input

The first line contains $n, m, q$ ($1 \le n \le 500$, $1 \le m, q \le 10^5$), representing the number of vertices, edges, and queries in the graph.

The next $m$ lines each contain three integers $u, v, c$ ($1 \le u, v \le n$, $0 \le c < 2^{64}$), representing an edge in the graph.

The next $q$ lines each contain two positive integers $l, r$ ($1 \le l \le r \le m$), representing a query.

It is guaranteed that the graph contains no self-loops, but it may contain multiple edges.

Output

For each query, output one line containing an integer representing the answer.

Example

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