נתון גרף עם $N$ קודקודים ו-$M$ קשתות לא מכוונות. לכל קשת $i$ יש דירוג מעבר $W_i$ והיא מחברת בין הקודקודים $U_i$ ו-$V_i$.

בוב רשאי לנוע מקודקוד אחד לאחר באמצעות קשתות. בוב יכול להשתמש בקשת ה-$i$ אם ורק אם הדירוג שלו גדול או שווה ל-$W_i$. הוא יכול להשתמש באותה קשת ולבקר באותו קודקוד כמה פעמים שירצה.

בכל פעם שבוב נמצא בקודקוד $x$, יש לו שתי אפשרויות להשגת דירוג חדש:

• הוא יכול להרוויח $A_x$ דירוג בחינם. הוא יכול להשתמש באפשרות זו פעם אחת בלבד במהלך המסע שלו.
• הוא יכול להרוויח $1$ דירוג תמורת $C_x$ מטבעות. הוא יכול להשתמש באפשרות זו כמה פעמים שירצה לאורך כל המסע שלו.

לבוב יש כעת $Q$ שאילתות. עבור כל שאילתה $i$, ענו על השאלה הבאה:

• לבוב יש דירוג התחלתי של $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