Молочні відвідування (Золото)
Фермер Джон планує побудувати n ферм, які будуть з'єднані n - 1 дорогами, утворюючи дерево (тобто всі ферми досяжні одна з одної, циклів немає). Кожна ферма містить корову з цілочисленим типом T[i] від 1 до n включно.
m друзів фермера Джона часто відвідують його. Під час візиту друга i фермер Джон буде йти з ним по унікальному набору доріг від ферми A[i] до ферми B[i] (можливо, що A[i] = B[i]). Крім того, вони можуть спробувати молока від будь-якої корови на своєму шляху. Оскільки більшість друзів фермера Джона також є фермерами, у них дуже сильні уподобання щодо молока. Кожен з його друзів буде пити молоко тільки від певної породи корів. Будь-який з друзів фермера Джона буде щасливий тільки в тому випадку, якщо зможе випити улюблений сорт молока під час свого візиту.
Визначте, чи буде щасливий кожен друг в результаті візиту.
Вхідні дані
Перша рядок містить два цілих числа n (1 ≤ n ≤ 10^5) і m (1 ≤ m ≤ 10^5). У другому рядку записано n цілих чисел T[1], T[2],..., T[n]. Тип корови на i-ій фермі позначається T[i].
Наступні n - 1 рядків містять по два різних цілих числа x і y (1 ≤ x, y ≤ n), що вказує на те, що між фермами x і y існує дорога.
У наступних m рядках записані цілі числа A[i], B[i] і C[i]. A[i] і B[i] представляють собою кінцеві точки шляху, пройденого під час відвідування друга i, тоді як C[i] (1 ≤ C[i] ≤ n) вказує на сорт корови, молоко якої любить пити друг.
Вихідні дані
Виведіть двійковий рядок довжини m. i-ий символ рядка повинен бути '1', якщо i-ий друг буде щасливий, і '0' в іншому випадку.
Приклад
У цьому прикладі шлях від 1 до 4 включає ферми 1, 2 і 4. Всі вони містять корів типу 1, тому перший друг буде задоволений, а другий - ні.