In country A, Little B has mastered a technique for precise weather forecasting.
Little B's forecasting technique relies on a machine, which is a tree with $n$ nodes rooted at $1$, where every node has an even number of children. For each node, there are two pieces of data: collected data and analyzed data.
Every day, Little B collects $n$ pieces of data from nature, each being $0$ or $1$. The $i$-th piece of data is loaded into the collected data of the $i$-th node of the machine.
When the data collection is complete, Little B starts the machine to calculate the analyzed data: the analyzed data of each node is the mode of the analyzed data of all its children and its own collected data.
After the calculation is finished, if the analyzed data of the root node is $1$, it will rain tomorrow; otherwise, it will not.
Unfortunately, the data collection process is not always straightforward. Little B has provided his estimates for these data: the probability that the $i$-th piece of data is $1$ is $p_i$, and all data distributions are independent. Little B wants you to help him quickly calculate the probability that it will rain tomorrow. Additionally, Little B sometimes updates some of the data; he will inform you of a change in the probability of one piece of data each time, and you need to provide the answer after each change. You only need to output the answer modulo $998244353$.
Input
The first line contains two integers $n$ and $q$, representing the number of nodes in the tree and the number of updates.
The next line contains $n - 1$ positive integers, where the $i$-th positive integer $anc_{i+1}$ represents the parent of node $i + 1$.
The next line contains $n$ integers $w_i$, where the initial $p_i = \frac{w_i}{998244354}$.
The next $q$ lines each contain two integers $pos_i$ and $v_i$, indicating that $p_{pos_i}$ is changed to $\frac{v_i}{998244354}$.
Output
A total of $q+1$ lines, each containing an integer representing the answer modulo $998244353$ initially and after each update.
Examples
Input 1
3 1 1 1 499122177 499122177 499122177 1 0
Output 1
499122177 748683265
Input 2
5 3 1 1 2 2 332748118 1 332748118 499122177 499122177 2 332748118 1 1 1 332748118
Output 2
776412275 850356301 942786334 850356301
Subtasks
For all data: $1 \leq n \leq 200000$, $1 \leq q \leq 50000$, and each node has an even number of children.
$0 \leq w_i, v_i \leq 998244353$
| Subtask ID | $n \leq$ | $q \leq$ | Special Property | Score |
|---|---|---|---|---|
| 1 | $n \leq 100$ | $q \leq 100$ | None | $12$ |
| 2 | $n \leq 200000$ | $q \leq 50000$ | A | $20$ |
| 3 | B | $20$ | ||
| 4 | C | $23$ | ||
| 5 | None | $25$ |
Property A: $anc_{2i} = anc_{2i+1}$, and they are generated uniformly at random in $[1, 2i - 1]$.
Property B: Each node has at most $10$ children.
Property C: $anc_i = 1$.