题目描述

Carol 有一个调色盘，可以用一棵 $n$ 个点且以 $1$ 为根的树来描述，其中每个节点 $i$ 上都有一个颜色 $c_i$。

定义一个颜色 $x$ 的强度是它在整棵树里出现的次数 $f_x$，一个颜色集合 $S$ 的美丽度是其中所有颜色的强度之积 $\prod_{x\in S} f_x$。

对于每个点 $u$，Carol 想知道，如果使用除了 $u$ 及其子树内出现过的颜色以外的所有颜色，调出的颜色的美丽度是多少。换言之，设以 $i$ 为根的子树里出现过的颜色集合是 $S_i$，则 Carol 想知道 $\prod_{x\in S_1\setminus S_u}f_x$ 的值。

由于答案可能很大，你只需要求出其对给定的 $M$ 取模后的结果。

输入格式

第一行两个整数 $n,M$。

第二行 $n$ 个整数 $c_{1\sim n}$。

第三行到第 $n+1$ 行，每行两个整数 $u,v$ 表示一条边。

输出格式

一行 $n$ 个整数，第 $i$ 个整数表示点 $i$ 的答案。

5 10
3 1 1 4 3
1 2
2 3
1 4
2 5

1 1 2 4 2

数据范围

对于 $20\%$ 的数据，$n\leq 2000$。

对于另外 $20\%$ 的数据，$1\leq c_i\leq 10$。

对于另外 $30\%$ 的数据，$M=998244353$。

对于 $100\%$ 的数据，$1\leq n\leq 5\times 10^5$，$1\leq c_i\leq n$，$1\leq M\leq 10^9$，$1\leq u_i,v_i\leq n$，$u_i\neq v_i$，保证输入的边构成一棵树。