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$ равен '1', если друг $i$ счастлив, иначе '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