Sama seperti banyak hal di dunia ini, judul masalah ini tidak memiliki arti apa pun.

Diberikan sebuah graf tak berarah dengan $n$ simpul dan $m$ sisi, sisi-sisinya dinomori dari $1$ hingga $m$ secara berurutan, dan setiap sisi memiliki bobot $c_i$. Sekarang Anda perlu menjawab $q$ kueri, masing-masing dalam bentuk berikut:

• Jika hanya sisi-sisi dengan indeks dalam $[l, r]$ yang dipertahankan, berapakah jumlah bobot dari semua sisi jembatan (bridge) pada graf tersebut modulo $2^{64}$?

Anda perlu menjawab setiap kueri.

Anda mungkin ingin mengetahui definisi jembatan: sebuah sisi disebut jembatan jika dan hanya jika penghapusannya meningkatkan banyaknya komponen terhubung pada graf.

Masukan

Baris pertama berisi $n, m, q$ ($1 \le n \le 500$, $1 \le m, q \le 10^5$), yang menyatakan banyaknya simpul, sisi, dan kueri pada graf.

$m$ baris berikutnya masing-masing berisi tiga bilangan bulat $u, v, c$ ($1 \le u, v \le n$, $0 \le c < 2^{64}$), yang menyatakan sebuah sisi pada graf.

$q$ baris berikutnya masing-masing berisi dua bilangan bulat positif $l, r$ ($1 \le l \le r \le m$), yang menyatakan sebuah kueri.

Dijamin bahwa graf tidak mengandung gelung (self-loop), tetapi mungkin mengandung sisi ganda.

Keluaran

Untuk setiap kueri, keluarkan satu baris yang berisi sebuah bilangan bulat yang menyatakan jawabannya.

Contoh

Masukan 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

Keluaran 1

7
14
28
56
18
0