กำหนดกราฟที่มี $N$ จุดยอด และมีเส้นเชื่อมไม่มีทิศทาง $M$ เส้น แต่ละเส้นเชื่อม $i$ มีเรตติ้งขั้นต่ำในการผ่านเท่ากับ $W_i$ และเชื่อมระหว่างจุดยอด $U_i$ กับ $V_i$

Bob สามารถเคลื่อนที่จากจุดยอดหนึ่งไปยังอีกจุดยอดหนึ่งโดยใช้เส้นเชื่อมได้ Bob จะสามารถใช้เส้นเชื่อมที่ $i$ ได้ก็ต่อเมื่อเรตติ้งของเขามากกว่าหรือเท่ากับ $W_i$ เท่านั้น เขาสามารถใช้เส้นเชื่อมเดิมและไปเยือนจุดยอดเดิมได้หลายครั้งเท่าที่ต้องการ

เมื่อใดก็ตามที่ Bob อยู่ที่จุดยอด $x$ เขามีสองทางเลือกในการเพิ่มเรตติ้งใหม่:

• เขาสามารถเพิ่มเรตติ้งได้ $A_x$ ฟรี เขาสามารถใช้ทางเลือกนี้ได้เพียงครั้งเดียวตลอดการเดินทางของเขา
• เขาสามารถเพิ่มเรตติ้งได้ $1$ โดยจ่าย $C_x$ เหรียญ เขาสามารถใช้ทางเลือกนี้ได้หลายครั้งเท่าที่ต้องการตลอดการเดินทางของเขา

ตอนนี้ Bob มีคำถาม $Q$ ข้อ สำหรับแต่ละคำถาม $i$ จงตอบคำถามต่อไปนี้:

• Bob มีเรตติ้งเริ่มต้นเท่ากับ $R_i$ และอยู่ที่จุดยอด $S_i$ เขาวางแผนที่จะเดินทางไปยังจุดยอด $T_i$ จำนวนเหรียญขั้นต่ำที่ต้องใช้ในการเดินทางนี้คือเท่าใด?

ให้แสดงผล $-1$ หากเขาไม่สามารถเดินทางไปยังจุดยอด $T_i$ ได้แม้จะมีจำนวนเหรียญไม่จำกัดก็ตาม

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

• บรรทัดแรกประกอบด้วยจำนวนเต็มหนึ่งตัว $T$ ($1 \le T \le 100$) คือจำนวนชุดข้อมูลทดสอบ
• จากนั้น สำหรับแต่ละชุดข้อมูลทดสอบ:
  • บรรทัดแรกประกอบด้วยจำนวนเต็มสามตัวที่คั่นด้วยช่องว่าง $N, M, Q$ ($1 \le N, M, Q \le 5 \cdot 10^5$)
  • บรรทัดที่สองประกอบด้วยจำนวนเต็ม $N$ ตัวที่คั่นด้วยช่องว่าง $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 10^6$)
  • บรรทัดที่สามประกอบด้วยจำนวนเต็ม $N$ ตัวที่คั่นด้วยช่องว่าง $C_1, C_2, \dots, C_N$ ($1 \le C_i \le 10^6$)
  • ถัดมาอีก $M$ บรรทัด แต่ละบรรทัดประกอบด้วยจำนวนเต็มสามตัวที่คั่นด้วยช่องว่าง $U_i, V_i, W_i$ ($1 \le U_i, V_i \le N; 1 \le W_i \le 10^{12}$)
  • ถัดมาอีก $Q$ บรรทัด แต่ละบรรทัดประกอบด้วยจำนวนเต็มสามตัวที่คั่นด้วยช่องว่าง $S_i, T_i, R_i$ ($1 \le S_i, T_i \le N; 1 \le R_i \le 10^{12}$)

รับประกันว่าผลรวมของ $N$ จากทุกชุดข้อมูลทดสอบจะไม่เกิน $5 \cdot 10^5$

รับประกันว่าผลรวมของ $M$ จากทุกชุดข้อมูลทดสอบจะไม่เกิน $5 \cdot 10^5$

รับประกันว่าผลรวมของ $Q$ จากทุกชุดข้อมูลทดสอบจะไม่เกิน $5 \cdot 10^5$

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

สำหรับแต่ละชุดข้อมูลทดสอบ ให้แสดงผล $Q$ บรรทัด แต่ละบรรทัดประกอบด้วยจำนวนเต็มหนึ่งตัว ซึ่งเป็นคำตอบของคำถามข้อนั้น

ตัวอย่าง

ข้อมูลนำเข้าตัวอย่าง 1

1
5 5 4
5 2 4 3 10
1 2 3 4 5
3 3 10
1 2 5
3 4 7
1 3 13
2 5 21
4 5 3
2 2 4
1 4 2
5 2 10

ข้อมูลส่งออกตัวอย่าง 1

11
0
4
5