J-Andeviking开公司(hard)_第二十届同济大学程序设计竞赛（同步赛）

时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

（本题与 easy 版本的不同之处仅仅在 $N$ 与 $Q$ 数据范围，并保证 easy 版的测试数据是 hard 版的测试数据的子集。若你的程序能通过 hard 版，则它同样可以通过 easy 版）

Andeviking 受够了打工人的生活。为了体验一下老板的感觉，他准备自己开一家公司，而一个公司能够高效运转的前提是该公司有一个高效的财务系统。由于 Andeviking 难以接受市面上现有系统的低效，他想让你这个水平高超的 acmer 帮他设计一套财务系统。

公司的人员按照职位高低可以构成一棵有根树，其中 1 号节点为根节点。每个节点的子节点可以看作是该节点的员工，每个节点也可以被看作是该节点的子节点的上司。每个人能且仅能修改自己员工的工资（他当然不可以自己给自己发工资）。每个人在公司中的等级定义为他上司的个数（上司的个数可以看作该点在树上的深度，其中 1 号节点的深度为 0），每人的初始工资将由输入给出。该财务系统需要支持以下五种操作：

$\bullet$ $1$ $p$ $x$ ,将编号为 $p$ 的人的工资改为 $x$ $({-10^6} \leq x \leq {10^6})$
$\bullet$ $2$ $p$ $k$ $x$ ,编号为 $p$ 的人将自己员工中比他恰好低 $k$ ( $1 \le k \leq 10^6$ )级的员工的工资全部改为 $x$ $({-10^6} \leq x \leq {10^6})$ ，若不存在这样的员工，则忽略此次操作
$\bullet$ $3$ $p$ $k$ $x$ ,编号为 $p$ 的人将自己员工中比他恰好低 $k$ ( $1 \le k \leq 10^6$ )级的员工的工资全部增加或减少 $x$ $({-10^6} \leq x \leq {10^6})$ ，正数代表增加，负数代表减少，0 代表不变，若不存在这样的员工，则忽略此次操作
$\bullet$ $4$ $p$ ,查询编号为 $p$ 的人的工资

$\bullet$ $5$ $p$ $k$ ，查询编号为 $p$ 的人的员工中比他恰好低 $k$ ( $1 \le k \leq 10^6$ )级的员工的工资和，若不存在这样的员工，输出 0

（请不要惊讶于工资可以是负数，作为一位凉心资本家，Andeviking 这样做是很正常的）

Andeviking 的耐心是有限的，他希望你在五小时内设计出满足要求的系统，作为报酬他会让志愿者送你一个气球。作为一个强大的 acmer ，请你帮帮 Andeviking 吧。

输入描述:

第一行一个正整数  ，代表公司中人员数量 

第二行  个整数 ，表示编号为  的人的初始工资为  

接下来  行，每行两个正整数 表示在有根树中  之间存在一条边 

接下来一个正整数  ，代表查询的次数 

接下来  行，每行一个指令，指令格式见上文描述，指令中每个参数由空格隔开，保证

输出描述:

每行一个整数，代表操作 4 和 5 的查询结果

示例1

输入

复制

输出

复制

3
-17
1