يخطط 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