Khu cắm trại ven Hồ Núi Cốc có ~N~ căn nhà gỗ, được đánh số từ ~1~ đến ~N~. Có ~N-1~ lối đi hai chiều nối các cặp nhà sao cho giữa hai nhà bất kỳ luôn có đúng một đường đi. Khoảng cách giữa hai nhà là số lối đi trên đường đi đó.

Ban quản lý lần lượt lắp đặt các bộ phát sóng và thực hiện truy vấn. Một bộ phát đặt tại nhà ~v~, có tần số ~f~ và bán kính ~d~, sẽ phủ mọi nhà cách ~v~ không quá ~d~. Các bộ phát đã lắp đặt không bị tháo bỏ.

Có ~Q~ thao tác thuộc một trong hai loại:

• ~1\ v\ f\ d~: lắp một bộ phát có tần số ~f~ và bán kính ~d~ tại nhà ~v~;

• ~2\ v~: tìm tần số lớn nhất trong các bộ phát đang phủ nhà ~v~. Nếu chưa có bộ phát nào phủ nhà ~v~, đáp án là ~-1~.

Input

• Dòng đầu chứa số nguyên ~N~ ~(3 \le N \le 100000)~;

• ~N-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ ~(1 \le u, v \le N)~, mô tả một lối đi. Các lối đi tạo thành một cây;

• Dòng tiếp theo chứa số nguyên ~Q~ ~(3 \le Q \le 100000)~;

• ~Q~ dòng cuối mô tả các thao tác theo một trong hai định dạng ở trên. Với thao tác loại ~1~, ~1 \le f \le 10^9~ và ~1 \le d < N~; mọi chỉ số nhà đều thuộc đoạn ~[1, N]~.

Output

• Với mỗi thao tác loại ~2~, in đáp án của truy vấn trên một dòng.

Scoring

Sample Input 1

10
1 2
1 3
2 4
2 5
3 6
3 7
5 8
6 9
7 10
10
2 4
1 5 12 2
2 8
1 9 20 3
2 4
2 7
1 4 17 5
2 10
2 6
2 5

Sample Output 1

-1
12
12
20
17
20
17

Notes

Truy vấn đầu tiên trả về ~-1~ vì chưa có bộ phát nào được lắp. Bộ phát tại nhà ~5~ phủ nhà ~8~ do hai nhà cách nhau một lối đi. Sau khi lắp bộ phát tại nhà ~9~, nhà ~7~ nhận được tần số ~20~, nên truy vấn tại đây trả về ~20~. Bộ phát tần số ~17~ tại nhà ~4~ có bán kính ~5~, vừa đủ phủ nhà ~10~.