#P17947. Cloud-Ascending Platform

Cloud-Ascending Platform

给定一个有 nn 个顶点、mm 条边的无向图,边按输入顺序编号为 11 到 mm,第 ii 条边的权值为 cic_i。

回答 qq 个询问。每个询问给定 [ℓ,r][\ell,r]:只保留编号在这个区间内的边,求所得图中所有桥的边权和,对 2642^{64} 取模。

一条边是桥,当且仅当删除它会使图的连通分量数增加。图不一定连通。

输入格式

第一行三个整数 n,m,qn,m,q(1≤n≤5001\le n\le500,1≤m,q≤1051\le m,q\le10^5)。

接下来 mm 行,每行三个整数 u,v,cu,v,c(1≤u,v≤n1\le u,v\le n,0≤c<2640\le c<2^{64}),表示一条无向边。

接下来 qq 行,每行两个整数 ℓ,r\ell,r(1≤ℓ≤r≤m1\le\ell\le r\le m)。

图没有自环,但允许重边。重边按各自的输入编号视为不同的边。

输出格式

每个询问输出一行一个整数,表示答案对 2642^{64} 取模后的值。

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

输出

7
14
28
56
18
0