Subtree Pair Value Sum on a Colored Tree

Masuko has a tree with \(n\) nodes, numbered from 1 to \(n\), with node 1 as the root. Each node \(i\) has a color \(c_i\) in the range \([1,k]\) (with \(k \le 15\)) and you are given a weight array \(a_1,a_2,\dots,a_k\). For any two nodes \(u\) and \(v\), define the value \(f(u,v)\) as follows:

Let \(u = p_1,p_2,\dots,p_m = v\) be the unique shortest path from \(u\) to \(v\). Define \[ f(u,v)=\prod_{i\in\{x\;|\;\exists\;j\in[1,m]\text{ such that }c_{p_j}=x\}}a_i. \] That is, \(f(u,v)\) is the product of \(a_i\) for every distinct color \(i\) that appears on the path from \(u\) to \(v\) (the formula uses \(\LaTeX\) for mathematical expressions).

For each node \(u=1,2,\dots,n\), let \(S_u\) be the set of all nodes such that on the unique path from the root to that node, \(u\) is visited (i.e. the subtree of \(u\)). You need to compute, for each \(u\), the sum \[ \sum_{x,y\in S_u,\;x\le y} f(x,y) \mod 998244353. \]

Print the answer for each node \(u\) (from 1 to \(n\)) on a separate line.

inputFormat

The first line contains two integers \(n\) and \(k\) -- the number of nodes and the number of colors.

The second line contains \(k\) integers: \(a_1,a_2,\dots,a_k\) (the weight for each color).

The third line contains \(n\) integers \(c_1,c_2,\dots,c_n\) representing the color of each node.

Then follow \(n-1\) lines, each containing two integers \(u\) and \(v\) representing an edge between nodes \(u\) and \(v\). The tree is undirected and rooted at node 1.

outputFormat

Output \(n\) lines, where the \(u\)th line contains the sum of \(f(x,y)\) over all unordered pairs \(x,y\) in the subtree of node \(u\) (with \(x\le y\)), modulo \(998244353\).

sample

3 2
2 3
1 2 1
1 2
1 3

21
3
2