$N$개의 정점과 $M$개의 무방향 간선으로 이루어진 그래프가 주어집니다. 각 간선 $i$는 통과 레이팅 $W_i$를 가지며 정점 $U_i$와 $V_i$를 연결합니다.

Bob은 간선을 이용해 한 정점에서 다른 정점으로 이동할 수 있습니다. Bob은 자신의 레이팅이 $W_i$ 이상일 때 그리고 그때에만 $i$번째 간선을 이용할 수 있습니다. 같은 간선을 원하는 만큼 여러 번 이용할 수 있으며 같은 정점도 원하는 만큼 여러 번 방문할 수 있습니다.

Bob이 정점 $x$에 위치할 때마다, 새로운 레이팅을 얻기 위해 두 가지 선택지를 사용할 수 있습니다:

• 무료로 $A_x$만큼의 레이팅을 얻을 수 있습니다. 이 선택지는 여정 전체에서 단 한 번만 사용할 수 있습니다.
• $C_x$개의 동전을 내고 $1$만큼의 레이팅을 얻을 수 있습니다. 이 선택지는 여정 내내 원하는 만큼 여러 번 사용할 수 있습니다.

Bob에게는 이제 $Q$개의 쿼리가 있습니다. 각 쿼리 $i$에 대해 다음 질문에 답하세요:

• Bob의 초기 레이팅은 $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