Trại ven hồ

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:

• $1vfd$: lắp một bộ phát có tần số $f$ và bán kính $d$ tại nhà $v$;
• $2v$: 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$.

Dữ liệu vào

• 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]$.

Dữ liệu ra

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

Ràng buộc

• $3\le N\le 100000$, $3\le Q\le 100000$
• $1\le f\le {10}^9$, $1\le d<N$

Subtasks

• Subtask 1 ($15\%$ số điểm): $N,Q\le 1000$.
• Subtask 2 ($15\%$ số điểm): cây là một đường thẳng.
• Subtask 3 ($20\%$ số điểm): nếu một đỉnh có ít nhất ba đỉnh kề thì không quá hai đỉnh kề của nó có bậc lớn hơn $1$.
• Subtask 4 ($20\%$ số điểm): có đúng một đỉnh có bậc lớn hơn $2$.
• Subtask 5 ($20\%$ số điểm): khoảng cách giữa hai đỉnh bất kỳ không vượt quá $30$.
• Subtask 6 ($10\%$ số điểm): không có giới hạn gì thêm.

Ví dụ