시간 제한메모리 제한제출정답맞힌 사람정답 비율
9 초 1024 MB53360.000%

문제

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 \le N \le 10^5$) --- 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 \le a_i, b_i \le N$, $a_i \ne b_i$, $1 \le w_i \le 10^4$), where $i$-th branch with weight $w_i$ connects vertices $a_i$ and $b_i$. The next line contains integer Q ($1 \le Q \le 10^5$) --- number of queries. In each of Q following lines there are two types of queries:

  1. Numbers 1, $v$, $d$, $c$ ($1 \le v \le N$, $0 \le d \le 10^9$, $0 \le c \le 10^9$).
  2. Numbers 2, $v$ ($1 \le v \le N$).

Input numbers are integers.

출력

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

예제 입력 1

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

예제 출력 1

6
6
0
5
7