เช่นเดียวกับสิ่งต่างๆ มากมายในโลกนี้ ชื่อของโจทย์ข้อนี้ไม่มีความหมายใดๆ

กำหนดกราฟไม่มีทิศทางที่มีจุดยอด $n$ จุด และเส้นเชื่อม $m$ เส้น โดยเส้นเชื่อมมีหมายเลขตั้งแต่ $1$ ถึง $m$ ตามลำดับ และแต่ละเส้นเชื่อมมีน้ำหนัก $c_i$ ตอนนี้คุณต้องตอบคำถาม $q$ ข้อ ซึ่งแต่ละข้ออยู่ในรูปแบบต่อไปนี้:

• หากเก็บไว้เฉพาะเส้นเชื่อมที่มีหมายเลขอยู่ในช่วง $[l, r]$ ผลรวมของน้ำหนักของเส้นเชื่อมที่เป็นสะพาน (bridge) ทั้งหมดในกราฟ มอดุโล $2^{64}$ มีค่าเท่าใด?

คุณต้องตอบคำถามแต่ละข้อ

คุณอาจต้องการทราบคำนิยามของสะพาน: เส้นเชื่อมหนึ่งจะถูกเรียกว่าสะพานก็ต่อเมื่อการลบเส้นเชื่อมนั้นออกทำให้จำนวนส่วนประกอบที่เชื่อมโยงกัน (connected components) ในกราฟเพิ่มขึ้น

ข้อมูลนำเข้า

บรรทัดแรกประกอบด้วย $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