Farmer John 计划建造 N（1≤N≤10$^5$）个农场，用 N−1条道路连接，构成一棵树（也就是说，所有农场之间都互相可以到达，并且没有环）。每个农场有一头奶牛，品种为1 到 N 之间的一个整数 T$_i$。Farmer John 的 MM 个朋友（1≤M≤10$^5$）经常前来拜访他。在朋友i 拜访之时，Farmer John 会与他的朋友沿着从农场 Ai 到农场 B$_i$ 之间的唯一路径行走（可能有 A$_i$=B$_i$）。除此之外，他们还可以品尝他们经过的路径上任意一头奶牛的牛奶。由于 Farmer John 的朋友们大多数也是农场主，他们对牛奶有着极强的偏好。他的每个朋友都只喝某种特定品种的奶牛的牛奶。任何 Farmer John 的朋友只有在他们访问时能喝到他们偏好的牛奶才会高兴。

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

测试点性质：

• 测试点 2 为以下第二个样例。
• 测试点 3 满足 N≤10$^3$,M≤2⋅10$^3$。
• 测试点 4-7 满足 C$_i$≤10（C$_i$定义见下）。

输入格式（文件名：milkvisits.in）：

输入的第一行包含两个整数 N 和 M。第二行包含 N 个空格分隔的整数 T$_1$,T$_2$,…,T$_N$。第i 个农场内的奶牛的品种用 T$_i$表示。

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

以下 M 行，每行包含整数 A$_i$，B$_i$，以及C$_i$。A$_i$ 和 B$_i$ 表示朋友 i 拜访时行走的路径的端点，C$_i$（1≤C$_i$≤N）表示这个朋友喜欢的牛奶的奶牛品种。

输出格式（文件名：milkvisits.out）：

输出一个长为 M 的二进制字符串。如果第 i 个朋友会感到高兴，则字符串的第 i 个字符为 '1'，否则为 '0'。

输入样例：

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

输出样例：

10110

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

输入样例：

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

输出样例：

0110