Как и многие вещи в этом мире, название этой задачи не имеет никакого смысла.

Дан неориентированный граф с $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