Bananabread và Tutel Master đang đi chơi arcade ở địa điểm N giấu tên. Ở đây, Tutel Master đã gặp một trò khá thú vị. Đầu tiên, máy sẽ cho Tutel Master một bản đồ được biểu diễn bằng ~N~ căn phòng có thể có kho báu được nối với nhau bởi ~N-1~ lối đi với lối đi thứ ~i~ có độ dài là ~w_i~ liên thông với nhau. Nghĩa là, luôn có duy nhất một đường đi từ mọi cặp căn phòng.

Máy cho bạn biết là vòng này máy sẽ làm ~Q~ hành động. Mỗi lượt, máy sẽ lựa chọn, thông báo cho Tutel Master và làm một trong hai hành động:

• ~1~ ~i~ ~w~: máy sẽ sử dụng ma thuật để mà biến độ dài lối đi thứ ~i~ thành độ dài ~w~ mới. Con đường thứ ~i~ sẽ có độ dài ~w~ này cho đến khi được biến đổi lại.

• ~2~ ~a~ ~b~: máy sẽ đặt bạn vào phòng thứ ~a~ và bạn phải tìm tổng độ dài phải đi để đến phòng thứ ~b~ để lấy kho báu. Tutel Master cần cho máy biết rằng tổng độ dài này.

Tutel Master chỉ có rất ít thời gian để trả lời hành động loại thứ hai. May rằng, Tutel Master biết là Bananabread có thể dễ dàng làm bài này. Vì Bananabread đang lo farm các trò khác nên đã nhờ bạn hỗ trợ Tutel Master. Bạn hãy giúp Tutel Master nhé.

Input

• Dòng đầu gồm một số nguyên dương ~N~ ~(1\le N \le 200000)~.

• ~N-1~ dòng tiếp theo, dòng thứ ~i~ gồm ba số là ~a_i,b_i,w_i~ là có cạnh giữa đỉnh ~a_i~ và ~b_i~ với độ dài là ~w_i~. ~(1\le a_i,b_i \le N,1\le w_i\le 10^9)~

• Dòng tiếp theo có một số nguyên dương ~Q~ ~(1\le Q \le 200000)~.

• ~Q~ dòng tiếp theo, mỗi dòng gồm ba số có dạng là ~1~ ~i~ ~w~ hoặc ~2~ ~a~ ~b~.

Output

• Gồm một số dòng là đáp án của các truy vấn loại ~2~

Scoring

Sample Input 1

5
1 2 3
1 3 6
1 4 9
4 5 10
4
2 2 3
2 1 5
1 3 1
2 1 5

Sample Output 1

9
19
11

Sample Input 2

7
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
5 6 1000000000
6 7 1000000000
3
2 1 6
1 1 294967296
2 1 6

Sample Output 2

5000000000
4294967296

Sample Input 3

1
1
2 1 1

Sample Output 3

0

Sample Input 4

8
1 2 105
1 3 103
2 4 105
2 5 100
5 6 101
3 7 106
3 8 100
18
2 2 8
2 3 6
1 4 108
2 3 4
2 3 5
2 5 5
2 3 1
2 4 3
1 1 107
2 3 1
2 7 6
2 3 8
2 1 5
2 7 6
2 4 7
2 1 7
2 5 3
2 8 6

Sample Output 4

308
409
313
316
0
103
313
103
525
100
215
525
421
209
318
519

Notes

Giải thích test ví dụ 1: