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.
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. 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 Hamilton).
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 Hamilton).

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 \times 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òng tiếp theo chứa một số nguyên dương ~q~ (~q \le 2 \times 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 \in \{1, 2, 3\}~.

Output

• Gồm 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.