世の中の多くのものがそうであるように、この問題のタイトルには何の意味もありません。

$n$ 個の頂点と $m$ 本の辺からなる無向グラフが与えられます。辺には順番に $1$ から $m$ までの番号が付けられており、各辺には重み $c_i$ があります。以下の形式の $q$ 個のクエリに答えてください。

• 番号が $[l, r]$ に含まれる辺のみを残したとき、グラフ内のすべての橋（bridge）である辺の重みの総和を $2^{64}$ で割った余りはいくらか？

各クエリに答える必要があります。

橋の定義は以下の通りです：ある辺が橋であるとは、その辺を取り除くことでグラフの連結成分の個数が増加すること、およびそのときに限ります。

入力

1 行目には、グラフの頂点数、辺数、クエリ数を表す $n, m, q$（$1 \le n \le 500$, $1 \le m, q \le 10^5$）が与えられます。

続く $m$ 行には、それぞれグラフの辺を表す 3 つの整数 $u, v, c$（$1 \le u, v \le n$, $0 \le c < 2^{64}$）が与えられます。

続く $q$ 行には、それぞれクエリを表す 2 つの正整数 $l, r$（$1 \le l \le r \le m$）が与えられます。

グラフに自己ループは含まれないことが保証されますが、多重辺が含まれる可能性はあります。

出力

各クエリについて、答えを表す整数を 1 行に出力してください。

入出力例

入力 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