问题描述

给定一棵有 $N$ 个顶点的根树。每个顶点都有一个编号 $1, \\, 2, \\, ..., \\, N$，其中顶点 $1$ 是这棵根树的根节点。第 $i(1 ≦ i ≦ N-1)$ 条边连接了顶点 $A_i$ 和顶点 $B_i$，是一条长度为 $C_i$ 的无向边。

给定 $Q$ 个查询，请按顺序处理这些查询。查询有 $2$ 种类型，并且输入格式和查询内容如下所示：

• 1 v k x：在以顶点 $v$ 为根的子树中，对于第 $k$ 代顶点与第 $k+1$ 代顶点之间的每条边，将其长度增加 $x$。其中，顶点 $v$ 被定义为第 $1$ 代顶点，而顶点的直接子节点是其下一代顶点，即第 $n+1$ 代顶点。
• 2 u v：求解从顶点 $u$ 到顶点 $v$ 的最短路径长度。

请查看示例 $1$ 以获取更多详细信息。

约束条件

• $1 ≦ N, \\, Q ≦ 10^{5}$
• $1 ≦ A_i, \\, B_i ≦ N$
• $1 ≦ C_i ≦ 10^{5}$
• $1 ≦ u, \\, v, \\, k ≦ N$
• $1 ≦ x ≦ 10^5$
• 给定的图是一棵树
• 类型为 $2$ 的查询中的顶点 $u, \\, v$ 是不同的
• $C_i, \\, x$ 都是整数

输入

输入通过标准输入提供，具体格式如下所示。

$N$ $A_1$ $B_1$ $C_1$ $:$ $A_{N-1}$ $B_{N-1}$ $C_{N-1}$ $Q$ $Query_1$ $:$ $Query_{Q}$

输出

对于格式为2 u v的查询，请按顺序逐行输出各个查询的答案。

示例 1

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

输出示例 1

20
27
6

开始时，给出的图如下所示。

处理 1 1 2 5 查询后，边的长度会发生如下变化。第 $2$ 代顶点（顶点 $2$ 和 $4$）与第 $3$ 代顶点（顶点 $3, \\ 5, \\ 6$）之间的边的长度都会增加 $5$。

再处理 1 4 1 2 查询后，边的长度会发生如下变化。顶点 $4$ 和第 $2$ 代顶点（顶点 $3, \\, 6$）之间的边的长度都会增加 $2$。

示例 2

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

输出示例 2

1

并不是所有边都会被增加。