세상의 많은 것들이 그렇듯, 이 문제의 제목에는 아무런 의미가 없다.

$n$개의 정점과 $m$개의 간선으로 이루어진 무방향 그래프가 주어지며, 간선에는 순서대로 $1$부터 $m$까지 번호가 매겨져 있고 각 간선은 가중치 $c_i$를 가진다. 이제 다음과 같은 형태의 질의 $q$개에 답해야 한다.

• 번호가 $[l, r]$에 속하는 간선들만 남겼을 때, 그래프에서 모든 단절선(bridge)의 가중치의 합을 $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