You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

水濑名雪见表哥还没回来，决定出去找他。

假设她的现在在节点 $1$ 上，她可以走的路径可以看作一棵 $n$ 个点的、以 $1$ 为根的树，每个点有权值 $w_i,a_i$。

现在她从根出发，假设位于点 $u$，且该点所有儿子的 $w_i$ 之和为 $s_i$，则她会以 $\dfrac{w_i}{s_i}$ 的概率走到节点 $i$。直到走到叶子为止。一次行走的得分为经过的点的 $a_i$ 之和。

现在有 $q$ 次修改，每次修改一个点的 $w_i$ 和 $a_i$。求初始状态和每次修改后，行走的期望得分。对 $998244353$ 取模。

Format

Input

第一行一个正整数 $n$。

第二行 $n-1$ 个正整数 $\text{fa}_i$ 表示 $[2,n]$ 号节点的父节点，保证 $1\le\text{fa}_i<i$。

第三行 $n$ 个正整数 $w_i$。

第四行 $n$ 个正整数 $a_i$。

第五行一个整数 $q$ 表示修改次数。

接下来 $q$ 行每行三个正整数 $u,w,a$，表示将 $u$ 号节点的权值赋值为输入的 $w,a$。

Output

$q+1$ 行，每行一个整数，表示在树的每一个状态下，得分的期望对 $998244353$ 取模的结果。

Samples

5
1 2 1 4
4 2 2 5 4
5 1 5 5 5
4
4 3 5
2 1 5
1 2 4
2 5 4

142606350
199648884
15
14
623902734

Explanations

样例的五个答案为 $\frac{97}7,\frac{67}5,15,14,\frac{107}8$。

Limitation

对于 $60\%$ 的数据，$1\le n,q\le 1000$。

对于 $100\%$ 的数据，$1\le n,q,w,a\le 10^5$，并保证任意时刻 $998244353\nmid s_i$。