Background

Klee likes living in trees.

Artist pid: 4787895.

Problem Description

Klee lives on a rooted tree, where the initial nodes are numbered from $1$ to $n$. To make it easier for Klee to travel, the people of Mondstadt decide to build one new road starting from every non-leaf node. Specifically, for each non-leaf node $u$, Mondstadt will uniformly randomly choose one node $v$ among its children, and build a new road between $u$ and $v$. Obviously, these newly built roads form many connected components. To help with their construction, you need to tell Mondstadt what the expected number of connected components is.

After hearing about this task, Klee thinks it is too easy for you. Therefore, she decides to add some modification operations on the tree:

• $\text{Add}\ u$: Add a child node under node $u$, numbered $n+i$, where $i$ is the operation index. It is guaranteed that node $u$ exists before the operation.
• $\text{Del}\ u$: Delete node $u$. It is guaranteed that node $u$ exists before the operation and is a leaf node.
• $\text{Upd}\ u$: Change the root of the tree to $u$. It is guaranteed that node $u$ exists before the operation.

Meanwhile, at any time, it is guaranteed that the tree will not be deleted until empty.

For the initial tree and the tree obtained after each modification, you need to answer the above question once. Note that the $m$ modifications are not independent, but the new roads built by Mondstadt each time are not affected by the results of the previous time.

Input Format

The first line contains an integer $n$, representing the size of the initial tree.

Lines $2$ to $n$ each contain an integer. The $i$-th of these lines gives $f_i$, the parent of node $i$ in the initial tree. Initially, node $1$ is the root of the tree.

Line $n+1$ contains an integer $m$, representing the number of modification operations.

Lines $n+2$ to $n+m+1$ each contain one modification operation, in the form described in Description.

Output Format

Output a total of $m+1$ lines.

Line $1$ is the answer for the initial tree.

Lines $2$ to $m+1$: line $i$ should output the answer after the $(i-1)$-th modification operation.

All outputs are taken modulo $998244353$. Specifically, if the answer is $\frac{p}{q}$, you should output an $x$ such that $xq\equiv p\pmod {998244353}$.

2
1
4
Add 1
Upd 2
Del 3
Del 1

1
2
1
1
1

Hint

$$\begin{array}{|c|c|c|c|}\hline \textbf{Test Point ID}& { n\le} & {m\le} & \textbf{Special Property} \cr\hline 1\sim 3 & 5 & 5 & - \cr\hline 4\sim 7 & 1000 & 1000 &- \cr\hline 8\sim 10 & 10^5 & 0 & - \cr\hline 11\sim 13 & 10^5 & 2\times 10^5 & \textbf{AB}\cr\hline 14\sim 16 & 2\times 10^5 & 5\times 10^4 & \textbf{A} \cr\hline 17\sim 20 & 2\times 10^5 & 2\times 10^5 & - \cr\hline \end{array}$$

• Special property $\textbf{A}$: It is guaranteed that there is no $\text{Upd}$ operation.
• Special property $\textbf{B}$: It is guaranteed that there is no $\text{Del}$ operation.

Constraints: for $100\%$ of the testdata, $1\le n,m\le 2\times 10^5$. It is guaranteed that $1\le f_i<i$.

Translated by ChatGPT 5