Farmer John planuje $N$ gospodarstw ($1 \leq N \leq 10^5$), połączonych $N-1$ drogami w drzewo: wszystkie są wzajemnie osiągalne, bez cykli. Każde ma krowę całkowitego typu $T_i$ od $1$ do $N$ włącznie.

Jego $M$ przyjaciół ($1 \leq M \leq 10^5$) często go odwiedza. Z przyjacielem $i$ przejdzie jedyną ścieżką od $A_i$ do $B_i$; możliwe jest $A_i = B_i$. Mogą próbować mleka dowolnej krowy po drodze. Większość przyjaciół też jest rolnikami i ma silne upodobania: każdy pije tylko mleko określonego typu krowy i będzie szczęśliwy tylko wtedy, gdy wypije ulubione mleko podczas wizyty.

Ustal, czy każdy przyjaciel będzie szczęśliwy po wizycie.

Wejście

Pierwszy wiersz zawiera całkowite $N$ i $M$.

Drugi zawiera $N$ całkowitych $T_1,T_2,\ldots, T_N$ oddzielonych spacjami. Krowa w gospodarstwie $i$ ma typ $T_i$.

Następne $N-1$ wierszy zawiera po dwie różne liczby całkowite $X$ i $Y$ ($1 \leq X, Y \leq N$), oznaczające krawędź między gospodarstwami $X$ i $Y$.

Następne $M$ wierszy zawiera $A_i$, $B_i$, $C_i$. $A_i$ i $B_i$ są końcami ścieżki przyjaciela $i$, a $C_i$ ($1\le C_i\le N$) ulubionym typem krowy.

Wyjście

Wypisz napis binarny długości $M$. Znak $i$ jest '1', jeśli przyjaciel $i$ będzie szczęśliwy, inaczej '0'.

Przykład

Wejście 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

Wyjście 1

10110

Uwagi

W przykładzie ścieżka z 1 do 4 przechodzi gospodarstwa 1, 2 i 4. Wszystkie krowy mają typ 1, więc pierwszy przyjaciel jest zadowolony, drugi nie.

Wejście 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

Wyjście 2

0110

Podzadania

• Test drugi jest drugim przykładem poniżej.
• Test trzeci spełnia $N\le 10^3, M\le 2\cdot 10^3$.
• Testy od czwartego do siódmego spełniają $C_i\le 10$ ($C_i$ zdefiniowano poniżej).

Autor zadania: Spencer Compton