포닉스의 마지막 춤이 시작된다. 다만 프로그래밍을 너무 열심히 공부한 탓에 춤 연습을 게을리 한 포닉스는 춤을 다음과 같이 구조화해 연습하기로 했다.

춤은 $N$개의 자세로 이루어져 있다. 각 자세는 $1$번부터 $N$번까지의 번호로 구분된다.

포닉스의 연습용 음원은 $K$개의 음으로 이루어져 있다. 각 음은 $1$ 이상 $K$ 이하의 정수로 표현된다. 각 음의 길이는 모두 $1$초로 같다. 연습 과정에서 $K$개의 음을 모두 재생했을 경우 다시 $1$번째 음부터 재생하는 것을 반복한다.

음악에 알맞은 자세를 취하는 것이 어려웠던 포닉스는 $M$개의 안무를 만들었다. $i$번 안무는 $(S_i, X_i, Y_i)$로 표현되며, 이는 현재 재생되는 음의 값이 $S_i$이고 포닉스가 $X_i$번 자세를 취하고 있을 경우, $Y_i$번 자세로 변경할 수 있음을 의미한다.

포닉스는 처음에 $1$번 자세를 취한 상태에서 연습을 시작한다. 각 음이 재생될 때마다 포닉스는 현재 자세를 유지하거나, 현재 재생되는 음의 값에 대응되는 안무 중 현재 자세에서 사용할 수 있는 안무 하나를 선택하여 자세를 한 번 변경할 수 있다.

바쁜 포닉스는 연습을 시작하기 전에 다음과 같은 질문의 답을 알고 싶어 한다.

• 연습을 $T$초 동안 진행했을 때, 즉 연습용 음원의 $1$번 음부터 재생해서 총 $T$개의 음이 재생될 때까지 연습했을 때 마지막에 포닉스가 취하고 있을 수 있는 자세의 개수는 몇 개일까?

이와 같은 형식으로 $Q$개의 질문이 주어질 때, 각 질문에 답하는 프로그램을 작성해 보자.

입력 형식

첫째 줄에 세 정수 $N$, $M$, $K$가 공백으로 구분되어 주어진다. ($2 \le N \le 200\ 000; 1 \le M \le 500\ 000; 1 \le K \le 500\ 000$)

둘째 줄에 $K$개의 정수 $A_1, A_2, \cdots, A_K$가 공백으로 구분되어 주어진다. $A_i$는 연습용 음원의 $i$번 음을 의미한다. ($1 \le A_i \le K$)

이후 $M$개의 줄에 걸쳐 $i+2$번째 줄에 $i$번 안무를 나타내는 세 정수 $S_i, X_i, Y_i$가 공백으로 구분되어 주어진다. ($1 \le S_i \le K; 1 \le X_i, Y_i \le N; X_i \neq Y_i$)

모든 $1 \le i < j \le M$에 대해 $(S_i, X_i, Y_i) \neq (S_j, X_j, Y_j)$임이 보장된다.

이후 질문의 수를 나타내는 정수 $Q$가 주어진다. ($1 \le Q \le 500\ 000$)

이후 $Q$개의 줄에 걸쳐 $i$번째 질문을 의미하는 정수 $T_i$가 차례대로 주어진다. ($1 \le i \le Q; 1 \le T_i \le 10^{12}$)

출력 형식

$Q$개의 줄에 걸쳐 각 질문에 대한 답을 나타내는 정수를 차례대로 출력한다.

예제

예제 1

입력

4 3 5
1 2 3 2 3
2 1 2
1 2 3
3 1 4
3
5
6
2

출력

3
4
2

예제 2

입력

6 6 5
5 2 3 1 3
1 1 2
5 1 3
2 3 4
3 4 2
2 2 5
5 2 5
3
3
6
5

출력

4
5
4