Farmer John מתכנן לבנות $N$ חוות ($1 \leq N \leq 10^5$), המחוברות ב-$N-1$ דרכים כעץ: כולן נגישות זו מזו ואין מעגלים. בכל חווה פרה מסוג שלם $T_i$ בין $1$ ל-$N$ כולל.

$M$ חבריו ($1 \leq M \leq 10^5$) מבקרים לעיתים קרובות. עם חבר $i$ הוא הולך במסלול היחיד מ-$A_i$ ל-$B_i$; ייתכן $A_i = B_i$. הם יכולים לטעום חלב מכל פרה במסלול. רוב החברים גם חקלאים ובעלי העדפות חזקות: כל אחד שותה רק חלב מסוג פרה מסוים, וישמח רק אם יוכל לשתות את החלב המועדף בביקור.

קבעו אם כל חבר יהיה שמח לאחר הביקור.

קלט

השורה הראשונה מכילה שלמים $N$ ו-$M$.

השנייה מכילה $N$ שלמים $T_1,T_2,\ldots, T_N$ המופרדים ברווחים. סוג הפרה בחווה ה-$i$ הוא $T_i$.

$N-1$ השורות הבאות מכילות שני שלמים שונים $X$ ו-$Y$ ($1 \leq X, Y \leq N$), המציינים קשת בין החוות $X$ ו-$Y$.

$M$ השורות הבאות מכילות $A_i$, $B_i$, $C_i$. $A_i$ ו-$B_i$ הם קצות מסלול חבר $i$, ו-$C_i$ ($1\le C_i\le N$) סוג הפרה המועדף.

פלט

הדפיסו מחרוזת בינרית באורך $M$. התו ה-$i$ הוא '1' אם החבר ה-$i$ יהיה שמח, אחרת '0'.

דוגמאות

קלט 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

פלט 1

10110

הערה

בדוגמה המסלול מ-1 ל-4 עובר בחוות 1, 2 ו-4. כולן עם פרות מסוג 1, ולכן החבר הראשון מרוצה והשני לא.

קלט 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

פלט 2

0110

תתי-משימות

• מקרה הבדיקה השני הוא הדוגמה השנייה למטה.
• המקרה השלישי מקיים $N\le 10^3, M\le 2\cdot 10^3$.
• המקרים הרביעי עד השביעי מקיימים $C_i\le 10$ ($C_i$ מוגדר למטה).

מחבר הבעיה: Spencer Compton