أُعطيَ رسم بياني يتكون من $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