Khoảng Cách Và Đỉnh Thứ K

Cho một cây gồm $N$ đỉnh, đánh số từ $1$ đến $N$. Mỗi cạnh có một trọng số nguyên dương. Với hai đỉnh $u,v$, đường đi duy nhất từ $u$ tới $v$ được xét theo đúng hướng bắt đầu ở $u$ và kết thúc ở $v$.

Cần xử lý $M$ truy vấn thuộc một trong hai loại:

• $1$ $u$ $v$: tính tổng trọng số các cạnh trên đường đi từ $u$ tới $v$;
• $2$ $u$ $v$ $k$: liệt kê các đỉnh trên đường đi từ $u$ tới $v$ theo thứ tự gặp được, đánh số từ $1$, rồi tìm đỉnh ở vị trí $k$.

Nếu $u=v$, đường đi không chứa cạnh nào, nên truy vấn loại $1$ có kết quả bằng $0$; truy vấn loại $2$ khi đó chỉ có thể có $k=1$.

Input

• Dòng đầu chứa số nguyên $N$.
• $N-1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a,b,w$: có một cạnh nối $a$ với $b$ và cạnh đó có trọng số $w$.
• Dòng tiếp theo chứa số nguyên $M$.
• Mỗi trong $M$ dòng cuối có một trong hai dạng:
• $1$ $u$ $v$;
• $2$ $u$ $v$ $k$.

Output

• Với mỗi truy vấn, in kết quả tương ứng trên một dòng.

Constraints

• $2\le N\le 10^5$.
• $1\le M\le 10^5$.
• $1\le a,b,u,v\le N$; $a\ne b$ trên mỗi cạnh.
• $1\le w\le 10^6$.
• $N-1$ cạnh tạo thành một cây.
• Với truy vấn loại $2,1\le k\le \text{soˆˊ đỉnh treˆn đường từ}u\text{tới}v$.
• Input chỉ chứa một test case.

Scoring

• Subtask $1$ ($50$ điểm): $N,M\le 2000$.
• Subtask $2$ ($50$ điểm): không có giới hạn bổ sung.

Example

8
1 2 4
1 3 7
2 4 3
2 5 6
3 6 5
6 7 2
6 8 9
7
1 4 7
2 4 7 1
2 4 7 3
2 4 7 6
2 7 5 3
1 8 5
2 6 6 1

21
4
1
7
3
31
6