{"raw_statement":[{"iden":"statement","content":"你打算建立一棵有 $(2n - 1)$ 个节点，其中有 $n$ 个叶子节点的二叉树。具体地，建立这棵树的伪代码如图所示。\n\n![1](https://cdn.luogu.com.cn/upload/image_hosting/eex8x40p.png)\n\n不难发现，节点 $1$ 是根节点，并且所有节点的编号与其 DFS 序相同。另外，你认为叶子节点十分重要，因此你按照节点编号从小到大又把这 $n$ 个叶子节点分别称为 $1$ 号叶子，$2$ 号叶子，$\\dots$，$n$ 号叶子。叶子节点会被其上方的节点管辖，具体来说，如果 $i$ 号叶子在节点 $j$ 的子树内，则称节点 $j$ 管辖 $i$ 号叶子，不妨用 $g(j,i)=1$ 表示；否则若节点 $j$ 不管辖 $i$ 号叶子，则 $g(j,i)=0$。注意，叶子节点同时也管辖自己本身。\n\n同时，你认为一个好的二叉树要有点权，于是对于节点 $i$，定义其点权为 $v_i$。初始所有节点的点权都为 $0$。\n\n在一次梦中，你正在改造这棵二叉树。你将会对这棵二叉树依次执行 $q$ 次操作，每次操作的格式和描述如下：\n- $1\\ s\\ t\\ v$：对于所有的整数 $i\\ (i\\in [s,t])$，将节点 $i$ 的点权加 $v$。\n- $2\\ s\\ t\\ v$：令 $\\mathcal{S}={\\textstyle \\bigcup_{i\\in [s,t]}}S_i$，其中 $S_i$ 表示节点 $i$ 管辖的叶子节点的集合。然后对于 $\\mathcal{S}$ 中所有叶子节点，将其点权加 $v$。注意 $\\mathcal{S}$ 是不重复集合，即在本次操作中，每个叶子节点最多被修改一次。\n- $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\n你还想再加点操作，但是早八的铃声把你吵醒了，不过你还是决定实现一下这个奇思妙想。"},{"iden":"input","content":"第一行包含一个整数 $n\\ (3\\le n\\le 10^5)$，表示二叉树中叶子节点的数量。\n\n第二行包含 $(2n-2)$ 个整数，其中第 $i$ 个整数表示节点 $i+1$ 的父亲节点编号。保证给出的树的形态与节点编号和题目所描述的相同。\n\n第三行包含一个整数 $q\\ (3\\le q\\le 10^5)$，表示操作次数。\n\n接下来 $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)$，表示一次询问操作。所有参数的含义如题目所述。"},{"iden":"output","content":"对于每个 $opt=3$ 的操作，输出一行一个整数，表示本次询问的结果。"}],"translated_statement":null,"sample_group":[["5\n1 2 3 3 2 1 7 7\n5\n1 2 4 3\n3 1 5\n2 5 7 5\n3 2 5\n3 1 5\n","18\n29\n38\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}