题目描述
给定一个长度为 $n$ 的序列 。你要支持区间加，维护区间和。
但显然这题没有这么简单。小 W 要求你在他给定的广义线段树上维护这个信息。
为了防止你自己写一棵线段树，祂给出了祂要求你的做法：
在每个节点上维护一个标记。最初，所有非叶子节点上的标记均为$0$，叶子节点的标记为其所对应数的权值。
要在节点 $[L,R]$ 将区间 $[l,r]$ 增加一个正整数 $k$ 时，若 $ 1\le L \le R \le r$ ，那么给这个节点加上一个标记 。否则，先下传该节点的标记，再递归与区间 $[l,r]$ 有交的孩子。每当有一个区间加 $[l,r,k]$ 时，在节点 $[1,n]$ 将区 间 $[l,r]$ 增加 $k$ 。
想必只要维护出标记，维护区间和也不是难事，所以小 $W$ 希望你维护每个节点的标记。
输入格式
第一行，$n,q$ ，表示序列长度与操作个数。
接下来一行 $n$ 个整数，表示序列 $A$ 的初始值。
接下来一行包含 $n-1$ 个整数，按照先序遍历给出了该线段树所有非叶子节点的划分位置 。即，节点
的左右孩子分别为 $[l,mid]$ 与 $[mid+1,r]$ 。不难发现通过这些信息就能唯一确定一棵 $[1,n]$ 上的线段树。
接下来 $q$ 行，每行形如 1 l r1 或 2 l r k ，表示询问点 $[l,r]$ 上的标记或者一次区间加。若是询问，保证 $[l,r]$ 恰好是线段树的某个节点。
输出格式
若干行，如题意所示。
样例1输入
6 7
1 1 1 1 1 1
5 1 3 2 4
2 2 5 2
1 2 5
2 2 4 1
1 2 5
1 2 3
1 4 4
1 5 5样例1输出
2
0
3
4
3样例1解释
见下发题目附件。
数据范围
| subtask | $n\le$ | $q\le$ | 特殊性质1 | 特殊性质2 |
|---|---|---|---|---|
| 1 | $100$ | $100$ | ||
| 2 | $10^5$ | $10^5$ | $\checkmark$ | $\checkmark$ |
| 3 | $10^5$ | $10^5$ | $\checkmark$ | |
| 4 | $5 \times 10^4$ | $5 \times 10^4$ | $\checkmark$ | |
| 5 | $2\times 10^5$ | $2\times 10^5$ |
$0\le A_i,k \le 10^3$
所有 subtask 分值均为 $20$ 分。 特殊性质 1：树为一条链。具体的，每个非叶子节点有一个儿子形如 $[i,i]$ 。
特殊性质 2：对于每个操作，其操作范围恰好是线段树的某个节点。