$N$ төбеден және $M$ бағытталмаған қырдан тұратын граф берілген. Әрбір $i$ қырының өту рейтингі $W_i$-ге тең және ол $U_i$ мен $V_i$ төбелерін қосады.

Бобқа қырларды пайдаланып бір төбеден екінші төбеге өтуге рұқсат етіледі. Боб $i$-ші қырды тек оның рейтингі $W_i$-ден үлкен немесе оған тең болған жағдайда ғана пайдалана алады. Ол бір қырды қалағанынша пайдалана алады және бір төбеге қалағанынша бара алады.

Боб $x$ төбесінде болған сайын, оның жаңа рейтинг алу үшін екі мүмкіндігі бар:

• Ол тегін түрде $A_x$ рейтинг ала алады. Ол бұл мүмкіндікті саяхаты барысында тек бір рет қана пайдалана алады.
• Ол $C_x$ тиынға $1$ рейтинг ала алады. Ол бұл мүмкіндікті саяхаты бойы қалағанынша көп рет пайдалана алады.

Бобта қазір $Q$ сұраныс бар. Әрбір $i$ сұранысы үшін келесі сұраққа жауап беріңіз:

• Бобтың бастапқы рейтингі $R_i$ және ол $S_i$ төбесінде орналасқан. Ол $T_i$ төбесіне жетуді жоспарлап отыр. Бұл үшін қажетті ең аз тиын саны қанша?

Егер ол шексіз тиын санымен де $T_i$ төбесіне жете алмаса, $-1$ шығарыңыз.

Кіріс деректер

• Бірінші жолда бір бүтін сан $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