Cho 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:

1. 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, nếu đỉnh ~u~ đang là màu đen thì đổi thành màu trắng;

2. 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 trên đồ thị đầy đủ này là khoảng cách giữa hai đỉnh màu đen tương ứng trên cây. Khoảng cách giữa hai đỉnh được tính bằng tổng trọng số các cạnh nằm trên đường đi đơn duy nhất giữa hai đỉnh trên cây. Trên đồ thị đầy đủ vừa xây dựng, tiến hành 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, mỗi đỉnh qua đúng một lần và quay về đỉnh xuất phát. Độ dài chu trình được tính bằng tổng trọng số của các cạnh thuộc chu trình;

3. 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ị đầy đủ vừa xây dựng, tiến hành tìm một đường đi có độ dài nhỏ nhất. Đường đi xuất phát từ một đỉnh bất kì, đi qua tất cả các đỉnh còn lại, mỗi đỉnh đi qua đúng một lần. Độ dài của đường đi được tính bằng tổng trọng số của các cạnh thuộc đường đi.

Yêu cầu: Hãy viết một chương trình xử lý ~q~ thao tác được cho.

Input

• Dòng thứ nhất chứa một số nguyên dương ~n~ ~(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 kí tự thứ ~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ó một cạnh nối giữa hai đỉnh ~u, v~ trên cây với trọng số ~c~. Dữ liệu bảo đảm ~n - 1~ cạnh này tạo thành một cây;

• Dòng tiếp theo chứa một số nguyên dương ~q~ ~(q \le 2 \cdot 10^5)~;

• Tiếp theo là ~q~ dòng, mỗi dòng chứa hai số nguyên dương ~t~ và ~u~ ~(1 \le u \le n)~ mô tả một thao tác, trong đó ~t = 1~ hoặc ~t = 2~ hoặc ~t = 3~ tương ứng là loại thao tác loại ~1~ hoặc loại ~2~ hoặc loại ~3~ và ~u~ là đỉnh được cho trong thao tác hiện tại. Dữ liệu bảo đảm đối với thao tác loại ~2~ và loại ~3~ có ít nhất một đỉnh màu đen thuộc cây con gốc ~u~.

Hai số liên tiếp trên cùng một dòng được ghi cách nhau bởi dấu cách.

Output

Ghi ra một số dòng, mỗi dòng là kết quả của các thao tác loại ~2~ hoặc loại ~3~ theo đúng thứ tự trong dữ liệu vào.

Scoring

Sample Input 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

Sample Output 1

18
12
24
12
12
0

Sample Input 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

Sample Output 2

11
6
14
6
6
0