Problem

From Juspay's OA

Given a tree with N nodes and N - 1 edges. It is rooted at the node R. Each edge between Nodes Ui and Vi has a weight Wi. From this, answer Q queries of the following 2 types :

1. Type 1 : 1 A B. Output the sum of all edge weights in the path from A to B
2. Type 2 : 2 A B x. Change the weight of the edge between U and V to x.

Input

1. N R Q
2. N - 1 lines describing edges : Ui, Vi, Wi
3. Q lines for each query

Output

For Type 1 queries, output the sum of all edge weights in the path from A to B

Constraints

• N <= 1e5
• Q <= 1e5
• Wi <= 1e9