Antifreeze

"In air so cold it stole my breath..."

The main building of Gyeonggi Science High School is a tree of $N$ classrooms connected by $N-1$ corridors. The corridor between classroom $U_i$ and classroom $V_i$ has length $W_i\ \text{m}$. ($1 \leq i \leq N-1$) Normally every classroom has a heater running, but at this school only some classrooms do. (This is really true!!) $A_i$ is $0$ if the heater in classroom $i$ is off, and $1$ if it is on. ($1 \leq i \leq N$) At least two classrooms have a working heater.

You start in a classroom with a working heater and want to reach another classroom with a working heater. Your temperature starts at $T$ and drops by $1$ every second. Your speed is $1\ \text{m/s}$, so you can think of your temperature dropping by the distance you walk. If the temperature becomes negative, you freeze to death. When you reach a classroom with a working heater, your temperature returns to $T$. Reaching a classroom with a working heater at the exact moment the temperature is $0$ is allowed.

You must answer $Q$ questions. The $i$-th question is: can you travel from classroom $X_i$ to classroom $Y_i$ without freezing? Both $X_i$ and $Y_i$ are classrooms with a working heater.

The first line contains the number of classrooms $N$ and the starting temperature $T$, separated by a space.

The second line contains $N$ integers $A_i$ ($1 \leq i \leq N$), separated by spaces.

The next $N-1$ lines describe the corridors. Line $i$ ($1 \leq i \leq N-1$) contains $U_i$, $V_i$, and $W_i$, separated by spaces.

The next line contains the number of questions $Q$.

The next $Q$ lines describe the questions. Line $i$ ($1 \leq i \leq Q$) contains $X_i$ and $Y_i$, separated by a space.

Print $Q$ lines. On line $i$, print $1$ if you can reach $Y_i$ from $X_i$ without freezing, and $0$ otherwise.

• $2 \leq N \leq 100{,}000$
• $1 \leq T \leq 10^9$
• $A_i \in \{0, 1\}$ ($1 \leq i \leq N$). At least two classrooms have a working heater.
• $1 \leq U_i, V_i \leq N$, $U_i \neq V_i$ ($1 \leq i \leq N-1$)
• The graph given by the input is a tree.
• $1 \leq W_i \leq 10^9$ ($1 \leq i \leq N$)
• The distance between any two classrooms does not exceed $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$)
• All numbers in the input are integers.