Giống như nhiều thứ trên thế gian này, tiêu đề của bài toán này không có ý nghĩa gì cả.

Cho một đồ thị vô hướng gồm $n$ đỉnh và $m$ cạnh, các cạnh được đánh số lần lượt từ $1$ đến $m$, và mỗi cạnh có trọng số $c_i$. Bây giờ bạn cần trả lời $q$ truy vấn, mỗi truy vấn có dạng như sau:

• Nếu chỉ giữ lại các cạnh có chỉ số nằm trong đoạn $[l, r]$, thì tổng trọng số của tất cả các cạnh cầu trong đồ thị chia lấy dư cho $2^{64}$ là bao nhiêu?

Bạn cần trả lời từng truy vấn.

Có thể bạn muốn biết định nghĩa về cạnh cầu: một cạnh được gọi là cầu khi và chỉ khi việc xóa nó làm tăng số thành phần liên thông trong đồ thị.

Dữ liệu vào

Dòng đầu tiên chứa $n, m, q$ ($1 \le n \le 500$, $1 \le m, q \le 10^5$), biểu thị số đỉnh, số cạnh và số truy vấn trong đồ thị.

$m$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $u, v, c$ ($1 \le u, v \le n$, $0 \le c < 2^{64}$), biểu thị một cạnh trong đồ thị.

$q$ dòng tiếp theo, mỗi dòng chứa hai số nguyên dương $l, r$ ($1 \le l \le r \le m$), biểu thị một truy vấn.

Đảm bảo rằng đồ thị không chứa khuyên, nhưng có thể chứa cạnh bội.

Kết quả

Với mỗi truy vấn, in ra một dòng chứa một số nguyên biểu thị câu trả lời.

Ví dụ

Dữ liệu vào 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

Kết quả 1

7
14
28
56
18
0