During the Lunar New Year, the village LQDOJ is decorated with a special Phúc Lộc Thọ tree, symbolizing good fortune, prosperity, and longevity. This tree has n nodes and n — 1 edges, where each edge (u₁, v₁) has a length w₁, (u₂, v₂) has a length w₂, and so on, representing connections between aspects of luck in the new year.

Shiba has been assigned the task of managing the Phúc Lộc Thọ tree throughout the Lunar New Year, performing q queries of two types:

Query Type 1: 1 x k n₁, n₂, ..., nₖ

Find the longest path from node x to a node y, ensuring that the path does not pass through any of the restricted nodes (n₁, n₂, ..., nₖ).

These nodes are restricted due to bad luck in the new year.

Query Type 2: 2 i w

Modify the length of edge i (uᵢ, vᵢ) to w.

However, Shiba's workload is overwhelming, and they cannot handle all the queries. Your task is to help Shiba by implementing a program to process these queries, and if successful, Flower_On_Stone will reward you with lucky money!

Input Format: The first line contains an integer n (1 ≤ n ≤ 200,000).

The next n — 1 lines contain three integers uᵢ, vᵢ, wᵢ (1 ≤ uᵢ, vᵢ ≤ n, 1 ≤ wᵢ ≤ 10⁹) representing the edges.

The next line contains an integer q (1 ≤ q ≤ 200,000).

The next q lines contain queries of type 1 x k n₁, n₂, ..., nₖ or 2 i w.

Constraints: In Query Type 1, it is guaranteed that x is not in {n₁, n₂, ..., nₖ}.

The restricted nodes n₁, n₂, ..., nₖ are distinct.

The sum of all k in Type 1 queries does not exceed 200,000.

Subtasks:

n, q ≤ 5000

Each node has at most degree 2.

k = 0 for all Type 1 queries.

No Type 2 queries.

No additional constraints.

Output Format: For each Query Type 1, output the length of the longest valid path. Can somebody give an editorial and a part of the code