Як і багато речей у цьому світі, назва цієї задачі не має жодного сенсу.

Задано неорієнтований граф із $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