Problem Statement

You are given a rooted tree with $N$ vertices numbered $1$ to $N$. Vertex $1$ is the root, and the parent of vertex $i$ $(2 \leq i \leq N)$ is vertex $p_i$ $(p_i < i)$. Additionally, there is a sequence $A = (A_1, A_2, \dots, A_N)$.

The hash value of the rooted tree is calculated as follows:

• Define $f(n)$ $(1 \leq n \leq N)$ as follows in the order $n = N, N-1, \dots, 2, 1$.
• If vertex $n$ is a leaf, $f(n) = A_n$.
  • If vertex $n$ is not a leaf, $\displaystyle f(n) = A_n + \prod_{c \in C(n)} f(c)$, where $C(n)$ is the set of children of $n$.
• The hash value of the rooted tree is $f(1) \bmod{998244353}$.

Process $Q$ queries in the order they are given. Each query provides $v$ and $x$, so update $A_v$ to $x$ and then compute the hash value of the rooted tree.

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq p_i < i$
• $0 \leq A_i < 998244353$
• $1 \leq v \leq N$
• $0 \leq x < 998244353$
• All input values are integers.

Input

The input is given from Standard Input in the following format, where $\mathrm{query}_i$ represents the $i$-th query:

N Q
p_2 p_3 \dots p_N
A_1 A_2 \dots A_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is given in the following format:

v x

Output

Print $Q$ lines. The $i$-th line should contain the answer to the $i$-th query.