D. БДБД
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Большая Древесная База Данных создана для того, чтобы в ней можно было надежно сохранить и раскрасить любое дерево. В новой версии БДБД запланирован новый функционал, для реализации которого потребуется вновь переосмыслить теорию графов.

В БДБД хранится взвешенное дерево. В языке запросов Системы Управления Большой Древесной Базы Данных (СУБДБД) предусмотрены два вида запросов:

  1. «1 v d c» — покрасить все вершины, находящиеся на расстоянии не более d от вершины v, в цвет c. Все вершины изначально окрашены в цвет с номером 0.
  2. «2 v» — вывести цвет вершины v.

Необходимо запрограммировать работу СУБДБД и ответить на все запросы пользователя.

Входные данные

В первой строке число N (1 ≤ N ≤ 105) — количество вершин дерева.

Следующие N - 1 строк содержат описание ребер, по три числа в строке ai, bi, wi (1 ≤ ai, bi ≤ N, ai ≠ bi, 1 ≤ wi ≤ 104), где i-ое ребро имеет вес wi и соединяет вершины ai и bi.

В следующей строке число Q (1 ≤ Q ≤ 105) — число запросов. В каждой из Q следующих строк запросы одного из двух видов:

  1. Числа 1, v, d, c (1 ≤ v ≤ N, 0 ≤ d ≤ 109, 0 ≤ c ≤ 109).
  2. Числа 2, v (1 ≤ v ≤ N).

Все числа во входных данных целые.

Выходные данные

Для каждого запроса второго типа необходимо вывести в отдельной строке цвет запрошенной вершины.

Примеры
Входные данные
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