问题描述

经过上一次的战略扩张，将业务发展到山区之后，公司今年的收益暴涨。然而 H 总却不打算奖赏为他打下江山的员工们，这让员工们非常不爽。负责财务小美不爽 H 老板的压榨很久了，于是她替老板做了个决定，给有功的员工们涨工资。

已知公司里一共有 $n$ 名员工，H 总作为公司的老板，员工号为 $1$。他们都具有上下级关系，每个人都有一个直接的上司（H 总除外），每个人都可以有若干个直接的下属。因此，如果把员工看做结点的话，他们的关系构成了一棵以 H 老板为根结点的树形结构。

已知小美总共进行了 $q$ 次涨工资的修改，修改有两种类型：

• 个人涨工资：将员工 $u$ 的月工资增加 $k$
• 部门集体涨工资：将员工 $u$ 领导的部门的所有人的月工资都增加 $k$

请计算经过小美的涨工资后，拼夕夕公司每个月一共要支付给员工多少月工资，以及每个员工的月工资各是多少。

输入格式

第一行两个整数 $n,q$。

接下来一行 $n$ 个整数，其中第 $i$ 个正整数 $e_i$ 表示员工 $i$ 的现在的月工资。

接下来 $n-1$ 行，每行两个整数 $u,v$，表示 $u$ 是 $v$ 的直接上司。

再接下来 $q$ 行，每行三个整数，$t,u,k$，其中 $t=1$ 时，表示进行的是个人涨工资操作，$t=2$ 时，进行的是部门集体涨工资操作，$u,k$ 即为上面所描述的含义，代表 $u$ 个人或者其所领导的部门的所有员工的工资增加 $k$。

输出格式

输出两行，第一行输出一个整数，表示所有员工的总工资。

第二行输出 $n$ 个整数，表示涨完工资后，每个人的工资 $e_1, e_2, ..., e_n$。

样例

8 6
10 4 3 5 9 1 7 2
1 2
1 4
4 7
5 6
4 8
2 5
2 3
1 1 10
2 1 10
2 5 4
1 3 20
1 6 4
2 4 3

172
30 14 33 18 23 19 20 15

组织结构如下图：

• 第 $1$ 次操作：将 $1$ 号员工的工资增加 $10$；
• 第 $2$ 次操作：所有人的工资都增加 $10$；
• 第 $3$ 次操作：将 $5,6$ 号员工的工资增加 $4$；
• 第 $4$ 次操作：将 $3$ 号员工的工资增加 $20$；
• 第 $5$ 次操作：将 $6$ 号员工的工资增加 $4$；
• 第 $6$ 次操作：将 $4,7,8$ 号员工的工资增加 $3$。

10 10
100 42 33 553 934 123 723 20 199 45
1 2
1 4
4 7
5 6
4 8
2 5
7 9
3 10
2 3
1 5 24
2 3 12
2 4 10
1 6 23
1 8 40
2 9 73
1 1 65
1 7 36
2 10 36
2 2 36

3313
165 78 81 563 994 182 769 70 282 129

数据范围

• $n,q \leq 10^5,\ e_i,k_i \leq 10^6$

• 数据保证 $1\le u\le n$，$e_i,k_i>0$。