Little R has recently become obsessed with a game. In the game, Little R's task is to capture some slimes. The game map has $n$ castles, numbered $1$ to $n$. There are $n-1$ undirected edges, each connecting two castles, and any two castles are connected. That is, these $n$ castles form a tree. In each castle, there are some red slimes and green slimes; castle $i$ has $r_i$ distinct red slimes and $g_i$ distinct green slimes. Little R starts from castle $1$. When he passes through a castle (including castle $1$), he captures exactly one slime from that castle (i.e., any one red slime or any one green slime; he cannot capture zero, and he cannot capture more than one), and then moves along an edge to a castle he has not visited before. If there are no unvisited castles, the game ends. That is, if castle $1$ is the root, the path Little R takes must be a chain from the root to some leaf node, and he captures exactly one slime in every castle he passes through.

Little R wants to capture exactly $k$ green slimes (no more, no less), and he wants to know how many different ways there are to do this. Scheme A and Scheme B are considered the same if and only if the set of slimes captured in Scheme A is exactly the same as the set of slimes captured in Scheme B. Note that any two slimes on the map are distinct. Since he has not yet decided on the specific value of $k$, you need to output the answers for $k=0, 1, 2, \dots, n$ simultaneously. Since the answers can be very large, you only need to output the answers modulo $998,244,353$.

Input

The input is read from standard input.

The first line contains a positive integer $n$ and a string $type$, representing the number of castles and the type of data, respectively. The $type$ string is provided to help you obtain partial points; you may not need to use this input. Its specific meaning is explained in the [Subtasks] section.

The second line contains $n$ positive integers, where the $i$-th integer represents $r_i$, the number of red slimes in castle $i$. It is guaranteed that $1 \le r_i \le 10^8$.

The third line contains $n$ positive integers, where the $i$-th integer represents $g_i$, the number of green slimes in castle $i$. It is guaranteed that $1 \le g_i \le 10^8$.

The next $n-1$ lines each contain two positive integers $u, v$, representing an edge between $u$ and $v$. The data is guaranteed to form a tree.

Output

Output to standard output.

Output $n+1$ lines, representing the answers for $k=0, 1, 2, \dots, n$, respectively.

Examples

Input 1

4 A1
3 2 2 1
2 4 1 3
1 2
1 3
3 4

Output 1

12
41
31
6
0

Note

Little R has $2$ possible routes: $1-2$ and $1-3-4$. Since at least one slime must be captured in every castle passed, the schemes corresponding to the two routes are always distinct. Suppose the route $1-2$ is chosen: if $k=0$, he must capture a red slime in both castle $1$ and castle $2$. Since these two castles have $3$ and $2$ distinct red slimes respectively, the number of ways is $3 \times 2 = 6$. If $k=1$, he can capture a red one in $1$ and a green one in $2$, or a green one in $1$ and a red one in $2$, so the number of ways is $3 \times 4 + 2 \times 2 = 16$. The number of ways for $k=2$ is $2 \times 4 = 8$. Similarly, if the route $1-3-4$ is chosen, the number of ways for $k=0, 1, 2, 3$ is $6, 25, 23, 6$. Therefore, the final answers are $12, 41, 31, 6, 0$.

Input 2

6 D1
7 3 2 5 9 1
2 6 4 4 4 3
1 6
2 5
3 5
3 4
5 6

Output 2

819
5197
10896
9036
3152
384
0

Subtasks

There are 20 test cases in this problem, each worth 5 points. The constraints for each test case are as follows:

Meaning of data types:

A: $r_i \le 5, g_i \le 5$ B: $r_i = g_i$ C: $g_i = 1$ D: No restrictions 0: A chain (castle $i$ is connected to castle $i+1$) 1: No restrictions

After submitting your code, the system will evaluate your solution against pre-test data and return the results. The pre-test data for this problem contains 8 test cases, with each test case having the same scale constraints as the corresponding rows in the table.

Note: The evaluation results of the pre-test data have no bearing on the final evaluation results.