Gấu có một cây gồm ~n~ đỉnh, các đỉnh được đánh số từ ~1~ tới ~n~, trong đó đỉnh ~1~ là đỉnh gốc. Mỗi cạnh của cây có trọng số là một số nguyên dương không quá ~10^9~. Ban đầu, mỗi đỉnh nhận một trong hai màu: đen hoặc trắng.

Có ~q~ thao tác cần được thực hiện một cách tuần tự, mỗi thao tác thuộc một trong ba loại sau:

• Thao tác loại 1: Nhận vào một đỉnh ~u~, tiến hành đổi màu đỉnh ~u~. Nếu đỉnh ~u~ đang là màu trắng thì đổi thành màu đen và ngược lại.

• Thao tác loại 2: Nhận vào một đỉnh ~u~, xét cây con gốc ~u~, xây dựng một đồ thị vô hướng đầy đủ có trọng số, trong đó mỗi đỉnh của đồ thị này tương ứng với một đỉnh màu đen thuộc cây con gốc ~u~. Trọng số của cạnh nối hai đỉnh trong đồ thị này là khoảng cách giữa hai đỉnh tương ứng trên cây (tính bằng tổng trọng số các cạnh trên đường đi đơn duy nhất giữa chúng). Trên đồ thị đầy đủ vừa xây dựng, tìm một chu trình có độ dài nhỏ nhất. Chu trình xuất phát từ một đỉnh bất kì, đi qua tất cả các đỉnh còn lại đúng một lần và quay về đỉnh xuất phát. Độ dài chu trình là tổng trọng số các cạnh thuộc chu trình.

• Thao tác loại 3: Nhận vào một đỉnh ~u~, xét cây con gốc ~u~, xây dựng một đồ thị vô hướng đầy đủ có trọng số tương tự như trong thao tác loại 2. Trên đồ thị này, tìm một đường đi có độ dài nhỏ nhất, đi qua tất cả các đỉnh đúng một lần (không cần quay về điểm xuất phát). Độ dài đường đi là tổng trọng số các cạnh thuộc đường đi.

Dữ liệu vào

• Dòng thứ nhất chứa một số nguyên ~n~ (~1 \leq n \le 2 \cdot 10^5~).
• Dòng thứ hai chứa một xâu nhị phân độ dài ~n~, trong đó kí tự thứ ~i~ là ~1~ nếu ban đầu đỉnh ~i~ có màu đen, ngược lại là ~0~.
• Tiếp theo là ~n - 1~ dòng, mỗi dòng chứa ba số nguyên dương ~u, v, c~ mô tả cạnh nối giữa hai đỉnh ~u, v~ với trọng số ~c~ ~(1 \leq u \neq v \leq n, 1 \leq c \leq 10^9)~.
• Dòng tiếp theo chứa số nguyên ~q~ ~(1 \leq q \le 2 \cdot 10^5)~.
• Tiếp theo là ~q~ dòng, mỗi dòng chứa hai số nguyên ~t~ và ~u~ (~1 \le u \le n~), mô tả một thao tác ~(1 \leq t \leq 3)~. Dữ liệu đảm bảo với thao tác loại ~2~ và ~3~ luôn tồn tại ít nhất một đỉnh màu đen trong cây con gốc ~u~.

Dữ liệu ra

Ghi ra các kết quả của các thao tác loại ~2~ và loại ~3~ theo đúng thứ tự xuất hiện, mỗi kết quả trên một dòng.

Ví dụ

Đầu vào 1

6
001110
1 2 1
1 4 2
4 6 3
2 5 2
2 3 4
9
2 1
1 4
2 1
1 6
2 1
2 2
1 4
2 2
2 5

Đầu ra 1

18
12
24
12
12
0

Đầu vào 2

6
001110
1 2 1
1 4 2
4 6 3
2 5 2
2 3 4
9
3 1
1 4
3 1
1 6
3 1
3 2
1 4
3 2
3 5

Đầu ra 2

11
6
14
6
6
0

Tính điểm

• Subtask ~1~ ~(14\%~ số diểm~)~: ~n, q \le 5000~, và trong các thao tác loại ~2, 3~ thì ~u = 1~.
• Subtask ~2~ ~(16\%~ số điểm~)~: Trong thao tác loại ~1~ chỉ đổi màu từ trắng sang đen, và trong các thao tác loại ~2, 3~ thì ~u = 1~.
• Subtask ~3~ ~(20\%~ số điểm~)~: Chỉ có thao tác loại ~1~ và loại ~2~, trong các thao tác loại ~2~ thì ~u = 1~.
• Subtask ~4~ ~(20\%~ số điểm~)~: Trong các thao tác loại ~2, 3~ thì ~u = 1~.
• Subtask ~5~ ~(30\%~ số điểm~)~: Không có ràng buộc gì thêm.