Фермер Джон планує побудувати \(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\)). Додатково вони пробують молоко кожної корови на своєму шляху. Оскільки друзі ФД також фермери, вони мають улюблене молоко. Кожен із них п'є молоко лише певного типу корів. Будь-який з друзів ФД буде щасливим, тільки якщо зможе попити свій улюблений тип молока під час шляху.

Визначте для кожного друга, чи буде він щасливим.

ОЦІНЮВАННЯ:

• Тест 2 другий приклад, наведений нижче.
• Тест 3 задовольняє \(N\le 10^3, M\le 2\cdot 10^3\).
• Тести 4-7 задовольняють \(C_i\le 10\) (\(C_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'.

Приклад вхідних даних

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