就好似呢個世界上嘅好多事物一樣，呢道題嘅標題冇任何意義。

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