D. LWDB
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

The first line contains an integer N (1 ≤ N ≤ 105) — the number of tree vertices. The following N-1 lines contain the description of branches, three numbers in each line ai, bi, wi (1 ≤ ai, bi ≤ N, ai ≠ bi, 1 ≤ wi ≤ 104), where i-th branch with weight wi connects vertices ai and bi. The next line contains integer Q (1 ≤ Q ≤ 105) — 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 ≤ 109, 0 ≤ c ≤ 109).
2. Numbers 2, v (1 ≤ v ≤ N).

Input numbers are integers.

Output

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

Examples
Input
51 2 301 3 503 4 703 5 6081 3 72 62 51 4 60 52 32 21 2 144 72 42 5
Output
66057