J. Jittery Roads
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You have just visited a country which consists of N cities, with exactly one path between every pair of cities(i.e. the country forms a weighted undirected tree with N vertices).

A non-empty subset of all the cities form a set of "special" cities. For every "special" city, you need to find what is the farthest distance from that city to any other "special" city. But since the country is still developing, the roads between two cities can change and the set of "special" cities also keep changing.

Input

First line contains N(1 ≤ N ≤ 105), followed by N - 1 lines each containing three values u v w, which means that there is a road between cities u and v with distance w(1 ≤ u, v ≤ N and 1 ≤ w ≤ 109).

The next line contains Q(1 ≤ Q ≤ 105), the number of queries. The next Q queries contain an integer 1 or 2 in one line, indicating the type of query.

For each type, the next line in the input is of the format:

  • u v w : Update the weight of edge between u and v to w(1 ≤ u, v ≤ N and 1 ≤ w ≤ 109).
  • An integer K(1 ≤ K ≤ N) followed by the K integers denoting the set of "special" cities for current query.

Note that sum of K over all queries  ≤ 5 * 105.

Output

For each query of type 2, print a single line with K values which is the answer for each of those "special" cities.

Example
Input
5
1 2 2
2 3 2
2 4 2
1 5 1
3
2
3 5 2 4
1
4 2 5
2
3 5 2 4
Output
5 3 5 
8 5 8
Note

For first query:

For city 5, city 4 is farthest "special city" at distance 5 and vice-versa. For city 2, city 5 is farthest "special city" at distance 3.