Tree and Queries 2

You are given a tree with N vertices. A tree is a connected undirected graph with no cycles. The vertices are numbered 1 to N and the edges are numbered 1 to N-1.

Exactly one path connects any two vertices of a tree. Write a program that answers the two queries below.

• 1 u v: print the cost of the path from u to v. The cost of a path is the sum of the costs of the edges on it.
• 2 u v k: print the k-th vertex on the path from u to v. Vertex u is the 1st vertex and vertex v is the last one.

The first line contains N (2 ≤ N ≤ 100,000).

Each of the next N-1 lines contains the two vertex numbers u and v joined by edge i, and the cost w of that edge. The value w is a natural number no greater than 1,000,000.

The next line contains the number of queries M (1 ≤ M ≤ 100,000).

Each of the next M lines contains one query. In a query of type 2, k is a natural number no greater than the number of vertices on the path from u to v.

Print the answer to each query on its own line, in the order the queries are given.