มีกราฟเชื่อมต่อ $G$ ประกอบด้วยจุดยอด $N$ จุด และเส้นเชื่อมไม่มีทิศทางที่มีน้ำหนัก $M$ เส้น ใน $G$ น้ำหนักของเส้นทางได้จากการ XOR น้ำหนักของเส้นเชื่อมทั้งหมดในเส้นทาง โปรดสังเกตว่าสามารถเดินตามเส้นเชื่อมเดียวหลายครั้งได้ ในกรณีนี้คุณจะ XOR น้ำหนักของเส้นเชื่อมนั้นตามจำนวนครั้งที่เดินผ่าน

สำหรับจุดยอด $u$ และ $v$ ให้ $d(u,v)$ เป็นน้ำหนักมากที่สุดของเส้นทางจาก $u$ ไป $v$

คุณต้องตอบคำถาม $Q$ ข้อในรูปแบบต่อไปนี้:

กำหนด $l$ และ $r$ ให้ จงหาค่า XOR ของ $d(i,j)$ สำหรับ $i$ และ $j$ ทุกคู่ที่ทำให้ $l \le i<j \le r$

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

บรรทัดแรกมีจำนวนเต็มสามจำนวน $N,M,Q$ ($1 \le N,M,Q \le 10^5$)

แต่ละบรรทัดใน $M$ บรรทัดถัดไปมีจำนวนเต็มสามจำนวน $u,v,w$ อธิบายเส้นเชื่อมน้ำหนัก $w$ ที่เชื่อมจุดยอด $u$ กับ $v$ ($1 \le u,v \le N$, $0 \le w<2^{30}$) โปรดสังเกตว่าโจทย์นี้อนุญาตให้มีเส้นเชื่อมซ้ำและลูป

แต่ละบรรทัดใน $Q$ บรรทัดถัดไปอธิบายคำถามหนึ่งข้อ และมีจำนวนเต็มสองจำนวน $l$ และ $r$ ($1 \le l<r \le N$)

ข้อมูลส่งออก

สำหรับแต่ละคำถาม พิมพ์คำตอบในบรรทัดแยกกัน

ตัวอย่าง

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

8 10 7
1 2 662784558
3 2 195868257
3 4 294212653
4 5 299265014
6 5 72652580
6 7 29303370
7 8 183954825
2 1 752722885
5 3 197591314
8 4 877461873
4 8
5 7
6 7
2 3
7 8
3 4
2 7

ข้อมูลส่งออก 1

0
713437792
738051848
716356296
736682272
1003204975
987493236