农夫约翰计划建造 $N$ 个农场，用 $N−1$ 条道路连接，构成一棵树（也就是说，所有农场之间都互相可以到达，并且没有环）。

每个农场有一头奶牛，品种为 $1$ 到 $N$ 之间的一个整数 $T_i$。

农夫约翰的 $M$ 个朋友经常前来拜访他。

在朋友 $i$ 拜访之时，农夫约翰会与他的朋友沿着从农场 $A_i$ 到农场 $B_i$ 之间的唯一路径行走（可能有 $A_i=B_i$）。

除此之外，他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。

由于农夫约翰的朋友们大多数也是农场主，他们对牛奶有着极强的偏好。

他的每个朋友都只喝某种特定品种的奶牛的牛奶。

任何农夫约翰的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。

请求出每个朋友在拜访过后是否会高兴。

输入格式

输入的第一行包含两个整数 $N$ 和 $M$。

第二行包含 $N$ 个空格分隔的整数 $T_1,T_2,…,T_N$。第 $i$ 个农场内的奶牛的品种用 $T_i$ 表示。

以下 $N−1$ 行，每行包含两个不同的整数 $X$ 和 $Y$，表示农场 $X$ 与 $Y$ 之间有一条边。

以下 $M$ 行，每行包含整数 $A_i，B_i$，以及 $C_i$。$A_i$ 和 $B_i$ 表示朋友 $i$ 拜访时行走的路径的端点，$C_i$ 表示这个朋友喜欢的牛奶的奶牛品种。

输出格式

输出一个长为 $M$ 的二进制字符串。

如果第 $i$ 个朋友会感到高兴，则字符串的第 $i$ 个字符为 ‘1’，否则为 ‘0’。

数据范围

$1 \le N \le 10^5$,
$1 \le M \le 10^5$,
$1 \le X,Y \le N$,
$1 \le C_i \le N$

输入样例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

输出样例1：

10110

样例1解释

在这个样例中，从农场 $1$ 到农场 $4$ 的路径包括农场 $1、2$ 和 $4$。这些农场中都是品种 $1$ 的奶牛，所以第一个朋友会感到满意，而第二个朋友不会。

输入样例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

输出样例2：

0110