Counting Non‐draw Rounds in a Tree Game

Two players, A and B, play a game on a rooted tree with n = 2m nodes (numbered from 1 to 2m) where node 1 is the root. Initially, Player A and Player B each "own" exactly m nodes – the two sets form a partition of the nodes. The game is played for m rounds. In each round, both players choose a node from their own set that has not been chosen before. Suppose in some round, Player A chooses node x and Player B chooses node y. The outcome of this round is determined as follows:

• If y lies in the subtree of x (i.e. the DFS interval of x contains that of y), then Player A wins the round.
• If x lies in the subtree of y, then Player A loses the round.
• Otherwise the round is a draw.

We are interested in the round in which the first non‐draw (i.e. win or loss) occurs. In order to compute its expected value over all random choices of the players, you decide to count the number of complete game cases (i.e. assignments of B’s choices corresponding to the fixed order in which A chooses his nodes) that result in exactly k rounds with a non‐draw outcome, for every k = 0,1,2,…,m.

Two cases are considered different if and only if there exists some node x in Player A’s set such that the node chosen by Player B in the round when x is selected is different between the two cases.

Since the total number of cases can be large, output every count modulo 998244353.

inputFormat

The input consists of four parts:

1. A single integer m.
2. A line with 2*m - 1 space‐separated integers: p₂, p₃, …, p_2*m, where p_i is the parent of node i (for 2 ≤ i ≤ 2*m). This defines the rooted tree (with node 1 as the root).
3. A line with m distinct space‐separated integers representing the nodes initially owned by Player A.
4. A line with m distinct space‐separated integers representing the nodes initially owned by Player B.

It is guaranteed that the tree has exactly 2*m nodes and that the two owned sets form a partition of the nodes.

outputFormat

Output m+1 space‐separated integers. The k-th integer (starting from k = 0) should be the number of cases, modulo 998244353, in which exactly k rounds result in a non‐draw outcome.

sample

1
1
1
2

0 1