Happy Farm Visitors

Farmer John plans to build (N) farms connected by (N-1) roads such that they form a tree (i.e. there is a unique path between any two farms). Each farm contains one cow with a breed type (T_i) (an integer between 1 and (N)).

Farmer John has (M) friends who visit him. During the (i)th visit, the friend travels along the unique path from farm (A_i) to farm (B_i) (note that (A_i) and (B_i) can be the same). While travelling, they can taste the milk from any cow on the path. Since each friend is also a farmer, they have a strong preference for milk from a particular breed. A friend will be happy if and only if they get to taste milk from a cow of their preferred breed during their visit.

Your task is to determine, for each friend, whether they will be happy after their visit.

inputFormat

The first line contains two integers (N) and (M) (the number of farms and the number of queries).

The second line contains (N) integers (T_1, T_2, \ldots, T_N), where (T_i) is the breed of the cow at farm (i).

Each of the next (N-1) lines contains two integers (u) and (v) describing a road between farms (u) and (v).

Each of the next (M) lines contains three integers (A_i), (B_i), and (P_i), where the (i)th friend travels from farm (A_i) to farm (B_i) and prefers the cow breed (P_i).

outputFormat

For each of the (M) queries, output a single line containing "1" if the friend is happy (i.e. there is at least one cow of breed (P_i) on the unique path from (A_i) to (B_i)), or "0" otherwise.

sample

3 3
1 2 3
1 2
2 3
1 3 2
1 3 3
2 2 1

1
1
0