就像世上的許多事物一樣，這道題的標題沒有任何意義。

給定一個含有 $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