Farmer John plant $N$ Bauernhöfe ($1 \leq N \leq 10^5$), verbunden durch $N-1$ Straßen zu einem Baum: Alle sind gegenseitig erreichbar, und es gibt keine Zyklen. Jeder Hof enthält eine Kuh mit ganzzahligem Typ $T_i$ zwischen $1$ und $N$ einschließlich.

Seine $M$ Freunde ($1 \leq M \leq 10^5$) besuchen ihn oft. Mit Freund $i$ geht er den einzigen Weg von Hof $A_i$ nach $B_i$; möglich ist $A_i = B_i$. Sie können Milch jeder Kuh entlang des Weges probieren. Die meisten Freunde sind auch Bauern mit starken Vorlieben: Jeder trinkt nur Milch eines bestimmten Kuhtyps und ist nur glücklich, wenn er beim Besuch seine bevorzugte Milch trinken kann.

Bestimme, ob jeder Freund nach dem Besuch glücklich sein wird.

Eingabe

Die erste Zeile enthält ganze Zahlen $N$ und $M$.

Die zweite enthält $N$ durch Leerzeichen getrennte ganze Zahlen $T_1,T_2,\ldots, T_N$. Die Kuh auf Hof $i$ hat Typ $T_i$.

Die nächsten $N-1$ Zeilen enthalten jeweils verschiedene ganze Zahlen $X$ und $Y$ ($1 \leq X, Y \leq N$), die eine Kante zwischen Höfen $X$ und $Y$ angeben.

Die nächsten $M$ Zeilen enthalten $A_i$, $B_i$, $C_i$. $A_i$ und $B_i$ sind die Endpunkte des Weges von Freund $i$, und $C_i$ ($1\le C_i\le N$) sein bevorzugter Kuhtyp.

Ausgabe

Gib eine binäre Zeichenfolge der Länge $M$ aus. Zeichen $i$ ist '1', wenn Freund $i$ glücklich wird, andernfalls '0'.

Beispiele

Eingabe 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

Ausgabe 1

10110

Hinweis

Im Beispiel führt der Weg von 1 nach 4 durch Höfe 1, 2 und 4. Alle Kühe haben Typ 1, daher ist der erste Freund zufrieden und der zweite nicht.

Eingabe 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

Ausgabe 2

0110

Teilaufgaben

• Testfall zwei ist das zweite Beispiel unten.
• Testfall drei erfüllt $N\le 10^3, M\le 2\cdot 10^3$.
• Testfälle vier bis sieben erfüllen $C_i\le 10$ ($C_i$ unten definiert).

Aufgabenautor: Spencer Compton