Problem Description

You are given a rooted tree with $ N $ vertices. Each vertex is numbered $ 1, 2, ..., N $, and vertex $ 1 $ is the root of this rooted tree. The $ i $th edge (for $1 \leq i \leq N-1$) connects vertex $ A_i $ and vertex $ B_i $ with an undirected edge of length $ C_i $.

You will be given $ Q $ queries to process in order. There are two types of queries, and their input format and content are as follows:

• 1 v k x: For each edge connecting the $ k $th generation vertices and $ k+1 $th generation vertices in the subtree rooted at vertex $ v $, add $ x $ to the length of that edge. Here, vertex $ v $ is defined as the $ 1 $st generation vertex, and vertices that are direct children of the $ n $th generation vertices are defined as the $ n+1 $th generation vertices.
• 2 u v: Find the shortest path length from vertex $ u $ to vertex $ v $.

Please refer to Sample 1 for more details.

Input Format

The input is given from the standard input in the following format:

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

Output Format

For each query of the format 2 u v, output the answer in one line in the order the queries are given.

Sample Input and Output

Sample Input #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

Sample Output #1

20
27
6

Sample Input #2

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

Sample Output #2

1

Notes/Hints

Constraints

• $1 \leq N, Q \leq 10^5$
• $1 \leq A_i, B_i \leq N$
• $1 \leq C_i \leq 10^5$
• $1 \leq u, v, k \leq N$
• $1 \leq x \leq 10^5$
• The given graph is a tree.
• The vertices $ u, v $ given in type 2 queries are distinct.
• $ C_i, x $ are integers.

Sample Explanation 1

Initially, the graph is given as shown in the figure below. After processing the query 1 1 2 5, the lengths of the edges change as shown in the figure below. $ 5 $ is added to the lengths of the edges connecting the $ 2 $nd generation vertices $ 2, 4 $ and the $ 3 $rd generation vertices $ 3, 5, 6 $. Further, after processing the query 1 4 1 2, the lengths of the edges change as shown in the figure below. $ 2 $ is added to the lengths of the edges connecting the $ 1 $st generation vertex $ 4 $ and the $ 2 $nd generation vertices $ 3, 6 $.

Sample Explanation 2

The edges to be added may not exist.

见题面 Input 部分

见题面 Output 部分