就像世上的许多事物一样，这道题的标题没有任何意义。

给定一个含有 $n$ 个顶点和 $m$ 条边的无向图，边按顺序从 $1$ 到 $m$ 编号，且每条边都有一个权值 $c_i$。现在你需要回答 $q$ 个询问，每个询问的格式如下：

• 如果只保留编号在 $[l, r]$ 范围内的边，图中所有桥边的权值之和模 $2^{64}$ 的值是多少？

你需要回答每个询问。

你可能需要了解桥的定义：一条边被称为桥，当且仅当删除它会增加图中的连通分量数量。

输入格式

第一行包含三个整数 $n, m, q$ ($1 \le n \le 500, 1 \le m, q \le 10^5$)，分别表示图中的顶点数、边数和询问数。

接下来的 $m$ 行，每行包含三个整数 $u, v, c$ ($1 \le u, v \le n, 0 \le c < 2^{64}$)，表示图中的一条边。

接下来的 $q$ 行，每行包含两个正整数 $l, r$ ($1 \le l \le r \le m$)，表示一个询问。

保证图中不包含自环，但可能包含重边。

输出格式

对于每个询问，输出一行，包含一个整数，表示该询问的答案。

样例

输入样例 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

输出样例 1

7
14
28
56
18
0