Antifreeze

"숨이 막힐 것 같이 차가웠던 공기 속에..."

경기과학고의 본관은 $N$개의 교실을 $N-1$개의 복도로 연결한 트리 구조이다. 교실 $U_i$와 교실 $V_i$ 사이에는 길이가 $W_i\ \text{m}$인 복도가 있다. ($1 \leq i \leq N-1$) 원래라면 모든 교실의 난방 기구가 작동해야 하지만, 경기과학고는 일부 교실에서만 난방 기구가 작동한다! (이거 진짜예요!!) $A_i$가 $0$이면 $i$번 교실의 난방 기구는 작동하지 않고, $1$이면 작동한다. ($1 \leq i \leq N$) 난방 기구가 작동하는 교실은 2개 이상 있다.

당신은 난방 기구가 작동하는 교실에서 출발해 다른 난방 기구가 작동하는 교실까지 가려고 한다. 처음 온도는 $T$이고, 온도는 1초마다 1씩 떨어진다. 당신의 속력은 $1\ \text{m/s}$이므로, 이동한 거리만큼 온도가 떨어진다고 생각해도 된다. 온도가 음수가 되면 얼어붙어서 사망한다. 난방 기구가 있는 교실에 도착하면 온도는 다시 $T$가 된다. 온도가 정확히 $0$인 시점에 난방 기구가 있는 교실에 도착하는 것은 허용된다.

$Q$개의 질문에 답해야 한다. $i$번째 질문은 다음과 같다. 교실 $X_i$에서 출발해 교실 $Y_i$까지 얼어붙지 않고 갈 수 있는가? 교실 $X_i$와 $Y_i$는 모두 난방 기구가 작동하는 교실이다.

첫째 줄에 교실의 개수 $N$과 시작 온도 $T$가 공백으로 구분되어 주어진다.

둘째 줄에 $N$개의 정수 $A_i$ ($1 \leq i \leq N$)가 공백으로 구분되어 주어진다.

이후 $N-1$개의 줄에 걸쳐 $i$번째 줄에 복도 정보 $U_i$, $V_i$, $W_i$가 공백으로 구분되어 주어진다. ($1 \leq i \leq N-1$)

다음 줄에 질문의 개수 $Q$가 주어진다.

이후 $Q$개의 줄에 걸쳐 $i$번째 줄에 $X_i$와 $Y_i$가 공백으로 구분되어 주어진다. ($1 \leq i \leq Q$)

$Q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 질문에 대해 얼어붙지 않고 $X_i$에서 $Y_i$까지 갈 수 있으면 $1$을, 갈 수 없으면 $0$을 출력한다.

• $2 \leq N \leq 100{,}000$
• $1 \leq T \leq 10^9$
• $A_i \in \{0, 1\}$ ($1 \leq i \leq N$). 난방 기구가 작동하는 교실은 2개 이상 있다.
• $1 \leq U_i, V_i \leq N$, $U_i \neq V_i$ ($1 \leq i \leq N-1$)
• 입력으로 주어지는 그래프는 트리 구조이다.
• $1 \leq W_i \leq 10^9$ ($1 \leq i \leq N$)
• 어떤 두 교실 사이의 거리도 $10^9\ \text{m}$를 넘지 않는다.
• $1 \leq Q \leq 100{,}000$
• $1 \leq X_i, Y_i \leq N$, $X_i \neq Y_i$, $A_{X_i} = A_{Y_i} = 1$ ($1 \leq i \leq Q$)
• 입력으로 주어지는 모든 수는 정수이다.