Условие задачи

В Соединённых Штатах JOI есть $N$ городов, пронумерованных от $1$ до $N$, и $M$ дорог, пронумерованных от $1$ до $M$. Дорога $i$ ($1 \le i \le M$) соединяет город $U_i$ и город $V_i$ в обоих направлениях.

Соединённые Штаты JOI состоят из $K$ штатов, пронумерованных от $1$ до $K$. Город $j$ ($1 \le j \le N$) принадлежит штату $S_j$. Кроме того, в каждом штате есть хотя бы $1$ город.

Директор K, министр промышленности Соединённых Штатов JOI, планирует провести $Q$ торговых операций. $k$-я торговая операция ($1 \le k \le Q$) заключается в перевозке фирменных товаров из города $A_k$ в город $B_k$ через некоторые дороги и города. Однако в этой операции сотрудничают только штат $S_{A_k}$ и штат $S_{B_k}$ (или только штат $S_{A_k}$, если $S_{A_k} = S_{B_k}$), и если маршрут проходит через любой город, не принадлежащий этим штатам, фирменные товары будут украдены.

Директор K хочет выяснить, существует ли маршрут перевозки, позволяющий провести торговлю без кражи фирменных товаров. По заданному расположению городов и дорог, а также информации о штатах и торговых операциях, напишите программу, которая для каждой операции определит, можно ли безопасно доставить фирменные товары.

Ограничения

• $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$).
• Для каждого $l$ ($1 \le l \le K$) существует $j$ ($1 \le j \le N$), такой что $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$).
• Все входные значения являются целыми числами.

Подзадачи

1. ($5$ баллов) $N \le 1\,000$, $M \le 1\,000$, $Q \le 1\,000$.
2. ($11$ баллов) Между любыми городами, принадлежащими штату $l$ ($1 \le l \le K$), можно перемещаться, проходя только по дорогам и городам, принадлежащим штату $l$.
3. ($42$ балла) $N \le 80\,000$, $M \le 80\,000$, $Q \le 80\,000$.
4. ($42$ балла) Дополнительных ограничений нет.

Входные данные

Входные данные подаются из стандартного потока ввода в следующем формате:

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

Выходные данные

В стандартный поток вывода выведите $Q$ строк. В $k$-й строке ($1 \le k \le Q$) выведите 1, если в $k$-й торговой операции возможно доставить фирменные товары, и 0, если это невозможно.

Пример 1

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

1
0
1

• $1$-я торговая операция заключается в перевозке фирменных товаров из города $1$ в город $2$ только через города, принадлежащие штату $1$ или штату $2$. Перевозка по маршруту город $1$ → город $2$ удовлетворяет условию, поэтому выводится 1.
• $2$-я торговая операция заключается в перевозке фирменных товаров из города $1$ в город $3$ только через города, принадлежащие штату $1$. Так как маршрута перевозки, удовлетворяющего условию, не существует, выводится 0.
• $3$-я торговая операция заключается в перевозке фирменных товаров из города $1$ в город $4$ только через города, принадлежащие штату $1$ или штату $2$. Перевозка по маршруту город $1$ → город $2$ → город $3$ → город $4$ удовлетворяет условию, поэтому выводится 1.

Этот пример входных данных удовлетворяет ограничениям подзадач $1, 3, 4$.

Пример 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

Этот пример входных данных удовлетворяет ограничениям подзадач $1, 3, 4$.

Пример 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

Этот пример входных данных удовлетворяет ограничениям всех подзадач.

Пример 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

Этот пример входных данных удовлетворяет ограничениям подзадач $1, 3, 4$.