Farmer John は $N$ 個（$1 \leq N \leq 10^5$）の農場を建て、$N-1$ 本の道路で木として結ぶ予定です。すべての農場間を移動でき、閉路はありません。各農場には整数の種類 $T_i$ の牛がおり、種類は $1$ から $N$ の範囲です。

$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