结果比较方式为全文比较（过滤行末空格及文末换行）。

题目描述

程老师名下有一家公司，公司设 $n$ 个部门，按 $1 \sim n$ 编号，其中 $1$ 号部门是总经理办公室。公司内部的层级用「直接上级」描述：除 $1$ 号部门外，每个部门恰好有一个直接上级部门，从任一部门沿直接上级一路上溯，最终必定到达 $1$ 号部门。财务为每个部门单独建一本台账，记录该部门累计收到的经费金额。

经费以拨款凭证的形式下发，每张凭证写明收款部门 $x$ 与金额 $v$（单位：万元）。凭证入账时，不只在部门 $x$ 处记账：从 $x$ 起沿直接上级一路上溯到 $1$ 号部门，沿途经过的每一个部门都各记 $v$ 万元入账。各本台账都是累加式的，不同凭证记下的金额互不覆盖，逐笔累加。

审计组不定期抽查。抽到部门 $x$ 时，审计组取出部门 $x$ 的管辖范围内所有部门的台账：$x$ 自身，以及它的全部下级部门、下级部门的下级，如此递归，直到没有下级的部门为止；把这些台账上的金额加总，作为本次抽查的结果。凭证入账与抽查按给定顺序依次发生，抽查统计的是该时刻各本台账上的累计金额。

现在给定公司的层级关系与这段时间内的全部操作记录，请逐条给出每次抽查的合计金额。

输入格式

从文件 fund.in 中读入数据。

• 第一行两个整数 $n, q$，表示部门数与操作条数；
• 接下来 $n-1$ 行，每行两个整数 $u, v$，表示部门 $u$ 与部门 $v$ 之间存在一条直接上下级关系：两者中恰有一个是另一个的直接上级，输入不标明先后；
• 接下来 $q$ 行，每行一条操作，格式为以下两种之一：
  • 1 x v：给部门 $x$ 下发一张金额为 $v$ 的拨款凭证；
  • 2 x：抽查部门 $x$ 的管辖范围。

输出格式

输出到文件 fund.out 中。

按操作出现的顺序，对每条 2 操作输出一行一个整数，表示该次抽查的合计金额。

样例

5 4
1 2
1 3
2 4
2 5
1 2 10
2 1
1 4 5
2 2

20
20

样例 1 解释

第一张凭证发给部门 $2$，金额 $10$：沿直接上级上溯的路径为部门 $2$、部门 $1$，这两本台账各加 $10$。此时抽查部门 $1$，它的管辖范围是部门 $1,2,3,4,5$，台账金额依次为 $10,10,0,0,0$，合计 $20$。

第二张凭证发给部门 $4$，金额 $5$：路径为部门 $4$、部门 $2$、部门 $1$，这三本台账各加 $5$。此时抽查部门 $2$，它的管辖范围是部门 $2,4,5$，台账金额依次为 $10+5=15$、$5$、$0$，合计 $20$。

7 7
1 2
1 3
4 3
3 5
4 6
4 7
1 6 4
2 4
1 1 3
2 4
2 6
1 5 2
2 3

8
8
4
16

样例 2 解释

层级关系是：部门 $1$ 的下级为部门 $2,3$；部门 $3$ 的下级为部门 $4,5$；部门 $4$ 的下级为部门 $6,7$。

第一张凭证（部门 $6$，$4$ 万元）：路径为部门 $6$、部门 $4$、部门 $3$、部门 $1$，这四本台账各加 $4$。抽查部门 $4$，管辖范围是部门 $4,6,7$，台账金额 $4,4,0$，合计 $8$。

第二张凭证（部门 $1$，$3$ 万元）：只有部门 $1$ 这本台账加 $3$。再抽查部门 $4$，管辖范围仍是部门 $4,6,7$，台账金额 $4,4,0$，合计 $8$。抽查部门 $6$，管辖范围只有它自己，台账金额 $4$，合计 $4$。

第三张凭证（部门 $5$，$2$ 万元）：路径为部门 $5$、部门 $3$、部门 $1$，这三本台账各加 $2$，其中部门 $3$ 的台账变为 $4+2=6$。抽查部门 $3$，管辖范围是部门 $3,4,5,6,7$，台账金额依次为 $6,4,2,4,0$，合计 $16$。

数据范围

对于所有测试数据，保证：

• $1 \le n, q \le 10^5$，$1 \le v \le 10^4$；
• 输入的 $n-1$ 对关系恰好构成一套完整层级：除 $1$ 号部门外每个部门在其中有且仅有一个直接上级部门，且从任一部门沿直接上级一路上溯必到达 $1$ 号部门；
• 操作行恰为 $q$ 行，每行的 $x$ 均为 $1 \sim n$ 中的整数。

各测试点的约束如下：

• 特殊性质 A：对于每个 $2 \le i \le n$，部门 $i-1$ 是部门 $i$ 的直接上级；
• 特殊性质 B：每条 1 操作中的部门 $x$ 都没有下级部门。