Farmer John prévoit $N$ fermes ($1 \leq N \leq 10^5$), reliées par $N-1$ routes formant un arbre : toutes sont accessibles entre elles, sans cycle. Chaque ferme possède une vache de type entier $T_i$ entre $1$ et $N$ inclus.

Ses $M$ amis ($1 \leq M \leq 10^5$) viennent souvent. Avec l'ami $i$, il parcourt l'unique chemin de $A_i$ à $B_i$ ; on peut avoir $A_i = B_i$. Ils peuvent goûter le lait de toute vache sur le chemin. La plupart des amis sont aussi fermiers et ont des préférences fortes : chacun ne boit que le lait d'un type de vache et ne sera heureux que s'il peut boire son lait préféré pendant la visite.

Déterminez si chaque ami sera heureux après sa visite.

Entrée

La première ligne contient les entiers $N$ et $M$.

La deuxième contient $N$ entiers $T_1,T_2,\ldots, T_N$ séparés par des espaces. La vache de la ferme $i$ est de type $T_i$.

Les $N-1$ lignes suivantes contiennent chacune deux entiers distincts $X$ et $Y$ ($1 \leq X, Y \leq N$), indiquant une arête entre les fermes $X$ et $Y$.

Les $M$ lignes suivantes contiennent $A_i$, $B_i$, $C_i$. $A_i$ et $B_i$ sont les extrémités du chemin de l'ami $i$, et $C_i$ ($1\le C_i\le N$) son type de vache préféré.

Sortie

Affichez une chaîne binaire de longueur $M$. Le caractère $i$ vaut '1' si l'ami $i$ est heureux, '0' sinon.

Exemples

Entrée 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

Sortie 1

10110

Remarque

Dans l'exemple, le chemin de 1 à 4 traverse les fermes 1, 2 et 4. Toutes ont des vaches de type 1 ; le premier ami est satisfait, le deuxième non.

Entrée 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

Sortie 2

0110

Sous-tâches

• Le test deux est le deuxième exemple ci-dessous.
• Le test trois vérifie $N\le 10^3, M\le 2\cdot 10^3$.
• Les tests quatre à sept vérifient $C_i\le 10$ ($C_i$ défini ci-dessous).

Auteur du problème : Spencer Compton