Каллiсто очолює клуб любителiв кави i зараз очiкує на приїзд багатьох гостей. Вiн планує вiдвiдати \(N\) кав’ярень, якi з’єднаннi \(N-1\) дорогою i ця сiтка дорiг утворює дерево. Кожна з цих кав’ярень має свiй фiрмовий кавовий напiй типу \(T_i\).

Очiкується приїзд \(M\) гостей. Пiд час приїзду гостя \(i\), Каллiсто разом з ним планує пройти унiкальним шляхом вiд кав’ярнi \(A_i\) до кав’ярнi \(B_i\) (можливий варiант \(A_i = B_i\) ). На своєму шляху вони будуть вживати кавовi напої. Кожен гiсть вiддає перевагу своїй улюбленi кавi i тому п’є тiльки її. Зрозумiло, що гiсть буде задоволеним лише тодi, коли вiн скуштує свiй улюблений тип кави.

Ваша задача визначити чи буде задоволений кожен iз гостей.

Формат вхідних даних

Перший рядок мiстить цiлi числа \(N\) i \(M\) \((1 \le N, M \le 10^5 )\).

Другий рядок мiстить \(N\) цiлих чисел \(T_1 , T_2 , ... , T_N\) . Тип фiрмового напою \(i\)-ї кав’ярнi позначається через \(T_i\) \((1 \le T_i \le N )\).

Далi iде \(N-1\) рядок, що мiстить цiлi числа \(X\) i \(Y\) \((1 \le X, Y \le N )\), якi вказують наявнiсть дороги мiж кав’ярнями \(X\) i \(Y\) .

Наступнi \(M\) рядкiв мiстять цiлi числа \(A_i , B_i , C_i\). \(A_i\) i \(B_i\) вказують на початкову та кiнцеву кав’ярню пiд час вiзиту \(i\)-го гостя, \(C_i\) \((1 \le C_i \le N )\) - тип улюбленої кави цього гостя.

Всi числа роздiляються одним пропуском.

Формат вихідних даних

Виведiть двiйковий рядок довжиною \(M\). \(i\)-й символ цього рядка має бути ’1’, якщо \(i\)-й гiсть буде задоволений, в 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

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

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

Пояснення

В першому прикладi шлях iз 1 в 4 проходить через кав’ярнi 1, 2, 4. Всi вони пропонують каву типу 1. Перший гiсть буде задоволеним, а другий - нi...