402046: GYM100633 D LWDB

The Large Wood Database is created to securely store and paint any existing tree. Update for LWDB provides new functionality, so it is time to think over the graph theory. A weighed tree is stored in the LWDB. In the query language for LWDB Management System (LWDB MS) two types of queries are available:

1. «1 v d c» — paint all tree-vertices at the distance not exceeding d from the vertice v in color c. Initial color for any vertices is 0.
2. «2 v» — return the color of the vertice v.

It is required to prototype LWDB MS and respond to all user’s queries.

The first line contains an integer N (1 ≤ N ≤ 10⁵) — the number of tree vertices. The following N-1 lines contain the description of branches, three numbers in each line a_i, b_i, w_i (1 ≤ a_i, b_i ≤ N, a_i ≠ b_i, 1 ≤ w_i ≤ 10⁴), where i-th branch with weight w_i connects vertices a_i and b_i. The next line contains integer Q (1 ≤ Q ≤ 10⁵) — number of queries. In each of Q following lines there are two types of queries:

1. Numbers 1, v, d, c (1 ≤ v ≤ N, 0 ≤ d ≤ 10⁹, 0 ≤ c ≤ 10⁹).
2. Numbers 2, v (1 ≤ v ≤ N).

Input numbers are integers.

For each second type query output the color of requested vertice in a separate line.

5
1 2 30
1 3 50
3 4 70
3 5 60
8
1 3 72 6
2 5
1 4 60 5
2 3
2 2
1 2 144 7
2 4
2 5

6
6
0
5
7