Problem Statement

In the United States of JOI, there are $N$ cities numbered from $1$ to $N$, and $M$ roads numbered from $1$ to $M$. Road $i$ ($1 \le i \le M$) connects city $U_i$ and city $V_i$ bidirectionally.

The United States of JOI consists of $K$ states numbered from $1$ to $K$. City $j$ ($1 \le j \le N$) belongs to state $S_j$. Also, every state contains at least $1$ city.

Director K, the Minister of Industry of the United States of JOI, is planning to conduct $Q$ trades from now on. The $k$-th trade ($1 \le k \le Q$) is to transport specialty products from city $A_k$ to city $B_k$ passing through some roads and cities. However, only state $S_{A_k}$ and state $S_{B_k}$ (or only state $S_{A_k}$ when $S_{A_k} = S_{B_k}$) cooperate in this trade, and if the route passes through any city not belonging to these states, the specialty products will be stolen.

Director K wants to investigate whether there exists a transport route to conduct the trade without the specialty products being stolen. Given the arrangement of cities and roads, and information about the states and trades, write a program to determine for each trade whether it is possible to safely deliver the specialty products.

Constraints

• $2 \le N \le 400\,000$.
• $1 \le M \le 400\,000$.
• $1 \le K \le N$.
• $1 \le U_i < V_i \le N$ ($1 \le i \le M$).
• $(U_i, V_i) \neq (U_j, V_j)$ ($1 \le i < j \le M$).
• $1 \le S_j \le K$ ($1 \le j \le N$).
• For every $l$ ($1 \le l \le K$), there exists $j$ ($1 \le j \le N$) such that $S_j = l$.
• $1 \le Q \le 400\,000$.
• $1 \le A_k \le N$ ($1 \le k \le Q$).
• $1 \le B_k \le N$ ($1 \le k \le Q$).
• $A_k \neq B_k$ ($1 \le k \le Q$).
• All input values are integers.

Subtasks

1. ($5$ points) $N \le 1\,000$, $M \le 1\,000$, $Q \le 1\,000$.
2. ($11$ points) All cities belonging to state $l$ ($1 \le l \le K$) can travel between each other passing only through roads and cities belonging to state $l$.
3. ($42$ points) $N \le 80\,000$, $M \le 80\,000$, $Q \le 80\,000$.
4. ($42$ points) No additional constraints.

Input

Input is given from Standard Input in the following format:

N M K
U_1 V_1
U_2 V_2
:
U_M V_M
S_1 S_2 ... S_N
Q
A_1 B_1
A_2 B_2
:
A_Q B_Q

Output

To Standard Output, output in $Q$ lines. On the $k$-th line ($1 \le k \le Q$), output 1 if it is possible to deliver the specialty products in the $k$-th trade, and 0 if it is impossible.

Sample 1

4 3 2
1 2
2 3
3 4
1 2 1 2
3
1 2
1 3
1 4

1
0
1

• The $1$-st trade is to transport specialty products from city $1$ to city $2$ passing only through cities belonging to state $1$ or state $2$. Transporting along city $1$ → city $2$ satisfies the condition, so output 1.
• The $2$-nd trade is to transport specialty products from city $1$ to city $3$ passing only through cities belonging to state $1$. Since no transport route satisfying the condition exists, output 0.
• The $3$-rd trade is to transport specialty products from city $1$ to city $4$ passing only through cities belonging to state $1$ or state $2$. Transporting along city $1$ → city $2$ → city $3$ → city $4$ satisfies the condition, so output 1.

This sample input satisfies the constraints of Subtasks $1, 3, 4$.

Sample 2

4 2 1
1 3
2 4
1 1 1 1
4
1 2
1 3
2 3
2 4

0
1
0
1

This sample input satisfies the constraints of Subtasks $1, 3, 4$.

Sample 3

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

1
0
1
1

This sample input satisfies the constraints of all subtasks.

Sample 4

8 11 3
4 8
1 8
4 6
3 5
2 4
7 8
6 7
3 4
1 4
2 3
3 8
2 3 1 1 2 1 2 1
10
8 2
8 1
2 7
5 3
5 7
4 8
1 8
6 8
6 5
1 8

1
1
0
1
0
1
1
1
1
1

This sample input satisfies the constraints of Subtasks $1, 3, 4$.