题号：NC217122
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld
题目描述
我们的李华去当交警啦！
交通网络呈树状（即n个点，n-1条边），1为根节点，某个时刻，李华可能会接到联络：
1：联络称某两点之间的道路发生堵塞，使得他们到达这两点之间的点的时间会增加
2：他们接到了一个紧急任务需要处理，即会在树的某个节点下方增加一个点
3：他们任务栏中的一个任务已经被完成了，即会删除树的某个节点（保证图始终连通）
输入描述:
第一行输入两个数n,m，表示点的个数和接到联络的个数
第二行输入n个数，表示初始到达第i个点的时间
接下来n-1行，每行两个数x,y表示x,y之间有一条边
接下来m行每行一个联络，具体如下
操作 1： 格式：1 x y k 含义：将x到y的路径上的点每个点的到达时间增加k
操作 2： 格式：2 x y含义：增加一个点，设这是第q次2操作，那么他的编号为n+q，他的初始到达时间为x，他的父亲为y
操作 3： 格式：3 x 含义：删除点x
特别提醒，由于栈大小的原因，请使用迭代层数较小的遍历方式
输出描述:
输出若干行，按序号升序排序
每行第一个数表示该点序号，第二个数表示到达当前点需要的时间（只输出目前未被删除的点）
示例1
输入
复制
6 4
0 0 0 0 0 0
1 2
1 3
2 4
2 5
5 6
1 4 6 1
2 0 5
1 4 7 1
3 6
说明
对于30%数据：n,m<=5000
对于另20%数据：保证没有2,3操作
对于另30%数据：保证没有3操作
对于100%数据：n,m<=500000，所有初始到达时间和增加的到达时间<=1000000