Problem Description

Farmer John plans to build $N$ farms connected by $N-1$ roads, forming a tree structure (meaning all farms are reachable from each other and there are no cycles). Each farm has a cow with a breed type represented by an integer $T_i$ between $1$ and $N$.

Farmer John's $M$ friends often visit him. During the visit of friend $i$, Farmer John and his friend will walk along the unique path from farm $A_i$ to farm $B_i$ (which might include $A_i = B_i$). Additionally, they can taste the milk from any cow they pass along this path. Since most of Farmer John's friends are also farmers, they have strong preferences for certain types of cow milk. Each friend only drinks milk from a specific breed of cow. A friend will be happy only if they can drink the milk of their preferred breed during their visit.

Determine whether each friend will be happy after their visit.

Input Format

The first line of input contains two integers $N$ and $M$.

The second line contains $N$ space-separated integers $T_1, T_2, \ldots, T_N$, where $T_i$ represents the breed type of the cow in the $i$-th farm.

The next $N-1$ lines each contain two distinct integers $X$ and $Y$ ($1 \leq X, Y \leq N$), indicating that there is an edge between farm $X$ and farm $Y$.

The next $M$ lines each contain three integers $A_i$, $B_i$, and $C_i$. $A_i$ and $B_i$ represent the endpoints of the path that friend $i$ will walk during their visit, and $C_i$ ($1 \leq C_i \leq N$) represents the preferred breed of cow milk for this friend.

Output Format

Output a binary string of length $M$. The $i$-th character of the string should be 1 if the $i$-th friend will be happy, and 0 otherwise.

Sample Input and Output

Input Sample #1

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

Output Sample #1

10110

Input Sample #2

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

Output Sample #2

0110

Notes/Hints

Test Case Properties:

Test case $2$ is the second sample input.

Test case $3$ satisfies $N \leq 10^3$ and $M \leq 2 \cdot 10^3$.

Test cases $4$ through $7$ satisfy $C_i \leq 10$.

For $100\%$ of the data, $1 \leq N \leq 10^5$ and $1 \leq M \leq 10^5$.

Problem contributed by Spencer Compton.

见题面 Input 部分

见题面 Output 部分