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