题目描述

你打算建立一棵有 $(2n - 1)$ 个节点，其中有 $n$ 个叶子节点的二叉树。具体地，建立这棵树的伪代码如图所示。

不难发现，节点 $1$ 是根节点，并且所有节点的编号与其 DFS 序相同。另外，你认为叶子节点十分重要，因此你按照节点编号从小到大又把这 $n$ 个叶子节点分别称为 $1$ 号叶子，$2$ 号叶子，$\dots$，$n$ 号叶子。叶子节点会被其上方的节点管辖，具体来说，如果 $i$ 号叶子在节点 $j$ 的子树内，则称节点 $j$ 管辖 $i$ 号叶子，不妨用 $g(j,i)=1$ 表示；否则若节点 $j$ 不管辖 $i$ 号叶子，则 $g(j,i)=0$。注意，叶子节点同时也管辖自己本身。

同时，你认为一个好的二叉树要有点权，于是对于节点 $i$，定义其点权为 $v_i$。初始所有节点的点权都为 $0$。

在一次梦中，你正在改造这棵二叉树。你将会对这棵二叉树依次执行 $q$ 次操作，每次操作的格式和描述如下：

• $1\ s\ t\ v$：对于所有的整数 $i\ (i\in [s,t])$，将节点 $i$ 的点权加 $v$。
• $2\ s\ t\ v$：令 $\mathcal{S}={\textstyle \bigcup_{i\in [s,t]}}S_i$，其中 $S_i$ 表示节点 $i$ 管辖的叶子节点的集合。然后对于 $\mathcal{S}$ 中所有叶子节点，将其点权加 $v$。注意 $\mathcal{S}$ 是不重复集合，即在本次操作中，每个叶子节点最多被修改一次。
• $3\ l\ r$：计算 $\sum^{r}_{i=l}f(i)\bmod 998\,244\,353$，其中 $f(i)$ 表示管辖 $i$ 号叶子的所有节点的点权之和，即 $f(i)=\sum_{g(j,i)=1}{v_j}$。

你还想再加点操作，但是早八的铃声把你吵醒了，不过你还是决定实现一下这个奇思妙想。

输入格式

第一行包含一个整数 $n\ (3\le n\le 10^5)$，表示二叉树中叶子节点的数量。

第二行包含 $(2n-2)$ 个整数，其中第 $i$ 个整数表示节点 $i+1$ 的父亲节点编号。保证给出的树的形态与节点编号和题目所描述的相同。

第三行包含一个整数 $q\ (3\le q\le 10^5)$，表示操作次数。

接下来 $q$ 行，每行第一个整数 $opt\ (opt\in [1, 3])$ 表示操作类型，若 $opt=1$ 或 $opt=2$，则紧跟三个整数 $s,t,v\ (1\le s\le t\le 2n-1,\ 0\le v<998\,244\,353)$，表示一次修改操作；若 $opt=3$，则紧跟两个整数 $l,r\ (1\le l\le r\le n)$，表示一次询问操作。所有参数的含义如题目所述。

输出格式

对于每个 $opt=3$ 的操作，输出一行一个整数，表示本次询问的结果。

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

18
29
38