Farmer John 打算建造 $N$ 个农场（$1 \leq N \leq 10^5$），用 $N-1$ 条道路连接成一棵树，即所有农场互相可达且没有环。每个农场有一头类型为整数 $T_i$ 的奶牛，类型在 $1$ 到 $N$ 之间，包含两端。

Farmer John 的 $M$ 位朋友（$1 \leq M \leq 10^5$）经常来访。朋友 $i$ 来访时，他们一起沿农场 $A_i$ 到 $B_i$ 的唯一路径散步，可能有 $A_i = B_i$。他们可以品尝路径上任意奶牛的牛奶。大多数朋友也是农民，对牛奶有强烈偏好，各自只喝某一种类型的奶牛的牛奶。朋友只有在来访时能喝到喜欢的类型，才会高兴。

请判断每位朋友来访后是否会高兴。

输入格式

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

第二行包含 $N$ 个用空格分隔的整数 $T_1,T_2,\ldots, T_N$。第 $i$ 个农场的奶牛类型为 $T_i$。

接下来 $N-1$ 行，每行包含两个不同整数 $X$ 和 $Y$（$1 \leq X, Y \leq N$），表示农场 $X$ 与 $Y$ 之间有一条边。

接下来 $M$ 行包含整数 $A_i$、$B_i$、$C_i$。$A_i$ 和 $B_i$ 为朋友 $i$ 散步路径的端点，$C_i$（$1\le C_i\le N$）表示他喜欢的奶牛类型。

输出格式

输出长度为 $M$ 的二进制字符串。第 $i$ 个字符在第 $i$ 位朋友高兴时为 '1'，否则为 '0'。

样例

输入格式 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 到 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

子任务

• 测试用例二是下方第二个样例。
• 测试用例三满足 $N\le 10^3, M\le 2\cdot 10^3$。
• 测试用例四至七满足 $C_i\le 10$（$C_i$ 定义见下方）。

题目作者：Spencer Compton