During a semester exam at UMT University, two students Phú, and Trung, were given a programming problem that simulates the internal infrastructure of the campus. The model is represented as a tree with ~N~ nodes, each node corresponding to a campus area such as a lecture hall, library, or laboratory. The connections between areas are modeled as edges, where each edge connects two nodes ~u_i~ and ~v_i~ and has an initial latency of ~w_i~.

The system must process ~Q~ queries, which fall into two types:

• Type 1 query: 1 ~i~ ~w~ - Phú updates the latency of the i-th connection (edge) to the new value ~w~.

• Type 2 query: 2 ~u~ ~v~ - Trung needs to calculate the total data transmission delay (i.e., the sum of edge weights) on the unique path from node ~u~ to node ~v~, ensuring efficient data flow between areas.

Meanwhile, Trung is responsible for verifying the output to ensure that every computation meets the problem's requirements. All queries are processed in order, and after each Type 2 query, the team must output the total delay along the current path between the two nodes.

Execute all queries in the given order. For each Type 2 query, print a single line containing the sum of weights on the path between the specified nodes ~u~ and ~v~.

Input

The first line contains an integer ~N~ ~(1 ≤ N ≤ 2 × 10^5)~, the number of nodes in the tree.

Each of the next N -1 lines contains three integers ~u_i~, ~v_i~, and ~w_i~ ~(1 ≤ u_i, v_i ≤ N, 1 ≤ w_i ≤ 10^9)~,describing the i-th edge connecting node ~u_i~ and node ~v_i~ with an initial weight (latency) of ~w_i~.

The next line contains an integer ~Q~ ~(1 ≤ Q ≤ 2 × 10^5)~ - the number of queries.

Each of the next Q lines contains a query in one of the following formats:

• 1 ~i~ ~w~ - Update the weight of the i-th edge to ~w~ ~(1 ≤ i ≤ N - 1, 1 ≤ w ≤ 10^9)~.

• 2 ~u~ ~v~ - Query the total weight on the path from node ~u~ to node ~v~ ~(1 ≤ u, v ≤ N)~.

It is guaranteed that there is at least one query of type 2.

Output

For each query of type 2, output a single line containing the total weight on the path from node ~u~ to node ~v~ at the time of the query.

Sample Input 1

5
1 2 3
1 3 6
1 4 9
4 5 10
4
2 2 3
2 1 5
1 3 1
2 1 5

Sample Ouput 1

9
19
11

Note:

Each query should be processed in the given order.

• The first query asks for the distance between vertex 2 and vertex 3. The path from 2 to 3 goes through edge 1 and edge 2, with a total weight of 9, so the output should be 9.

• The second query asks for the distance between vertex 1 and vertex 5. The path goes through edge 3 and edge 4, with a total weight of 19, so the output should be 19.

• The third query updates the weight of edge 3 to 1.

• The fourth query again asks for the distance between vertex 1 and vertex 5. The updated path (edge 3 and edge 4) now has a total weight of 11, so the output should be 11.