Migrated from Lutece 2930 末日时在做什么？有没有空？可以来数兔子吗？

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Tag:重链剖分维护矩阵 or 重链剖分维护斐波那契通项公式

给定一棵$n$个点的有根树(即$n$个点、$n-1$条边的连通图)，点编号$1$到$n$，根节点为$1$号点。 每个点$u$都有两种权值：A类权值$a_u$和B类权值$b_u$。以下修改操作都针对A类权值$a_u$，而B类权值$b_u$则是A类权值$a_u$的函数，随A类权值的变化而变化，且二者恒满足$b_u=f_{a_u}$。其中$f_i$表示斐波那契数列（兔子数列）的第$i$项的值。 你需要写一个数据结构实现以下操作：

1. 修改操作：给定参数$u$和$x$，表示让$u$子树内所有点的A类权值都加上$x$。
2. 询问操作：给定参数$u$，表示询问$u$的子树内所有点的B类权值之和。
3. 修改操作：给定参数$u$、$v$和$x$，表示让$u$到$v$路径上所有点（包括$u$和$v$）的A类权值都加上$x$。
4. 询问操作：给定参数$u$、$v$，表示询问$u$到$v$路径上所有点（包括$u$和$v$）的B类权值之和。 由于结果可能很大，你只需要输出询问答案对$998244353$取模的结果。

Input

第一行是一个整数$n$，表示点的个数。 第二行是$n$个整数，第$i$个整数表示点$i$的初始A类权值。 第三行是$n-1$个整数，第$i$个整数表示点$i+1$的父节点编号。 第四行是一个整数$m$，表示操作总数。 接下来$m$行，每行用若干个整数描述一次操作，每行第一个整数记作$opt$。 若$opt=1$，则接下来有两个整数$u$和$x$，表示让点$u$子树内所有点的A类权值都加上$x$。 若$opt=2$，则接下来有一个整数$u$，表示询问点$u$的子树内所有点的B类权值之和。 若$opt=3$，则接下来有三个整数$u$、$v$和$x$，表示让$u$到$v$路径上所有点（包括$u$和$v$）的A类权值都加上$x$。 若$opt=4$，则接下来有两个整数$u$、$v$，表示询问$u$到$v$路径上所有点（包括$u$和$v$）的B类权值之和。

Output

对于每一次询问操作，输出一行一个整数，表示答案对$998244353$取模的结果。

Samples

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

14
9
5
13

Constraints

$1\le n,m\le 10^5,1\le u,v\le n,1\le x,a_i\le 10^9$

Note

1. 树是指$n$个点、$n-1$条边的连通图，树上任意两点间都有且只有一条路径。如果$u$到根的路径经过了$v$，则认为$u$在$v$的子树内。特别地，$u$在$u$的子树内。
2. 斐波那契数列$f_i$满足以下递推式： $f_1=f_2=1,f_i=f_{i-1}+f_{i-2}(i>2)$
3. 对于取模的意义下的运算，加法、减法和乘法正常运算后取模即可，除法需要借助逆元转化为乘法运算。如果你不知道逆元的概念，也没关系，你只需要知道：在模$998244353$意义下，形如$a/b$的运算等价于$a*b^{998244351}$。至于如何快速计算$b^{998244351}$，请自行百度并掌握快速幂这一基本技巧。如果没有学习过逆元的基本概念，建议尽快了解费马小定理的内容，学习逆元的快速幂求法和线性递推求法，因为类似的取模运算在各个专题均可能高频率出现。

Resources

2023 UESTC ICPC Training for Data Structures