一个小女孩非常喜欢树上的问题。这是其中之一。
树是无向连通图,不包含环。树中节点 x 的度是树的节点 y 的数量,使得每个节点都通过树的某些边与节点 x 连接。
让我们考虑一棵由 n 个节点组成的树。我们将考虑索引从 1 到 n 的树节点。所考虑的树具有以下性质:除了节点号1之外的每个节点的度至多为2。
最初,树的每个节点都包含数字 0。您的任务是快速处理两种类型的请求:
- 表格请求:0 v x d。为了响应该请求,您应该将 x 添加到写入距离节点 v 至多 d 的节点中的所有数字。两个节点之间的距离是它们之间最短路径上的边数。
- 表单请求:1 v。在回复请求时,您应该打印节点 v 中写入的当前编号。
输入
第一行包含整数 n (2 ≤ n ≤ 105) 和 q (1 ≤ q ≤ 105) — 相应地,树节点的数量和请求的数量。
接下来的 n - 1 行中的每一行都包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n, ui ≠ vi),这表明节点 ui 和 vi 之间存在一条边。每条边的描述在输入中只出现一次。保证给定的图是具有语句中描述的属性的树。
接下来 q 行描述请求。
- 添加请求具有以下格式:0 v x d (1 ≤ v ≤ n, 1 ≤ x ≤ 104, 1 ≤ d < n)。
- 打印节点值的请求具有以下格式:1 v (1 ≤ v ≤ n)。
行中的数字由单个空格分隔。
输出
对于每个打印节点值的请求,打印一个整数 - 对请求的答复。
示例
输入 #1
3 6 1 2 1 3 0 3 1 2 0 2 3 1 0 1 5 2 1 1 1 2 1 3
输出 #1
9 9 6
输入 #2
6 11 1 2 2 5 5 4 1 6 1 3 0 3 1 3 0 3 4 5 0 2 1 4 0 1 5 5 0 4 6 2 1 1 1 2 1 3 1 4 1 5 1 6
输出 #2
11 17 11 16 17 11