Cho cây gồm ~N~ đỉnh, mỗi đỉnh ~u~ có trọng số cố định ~W[u]~. Ban đầu, tất cả các đỉnh đều màu Trắng. Xử lý các thao tác theo thứ tự:

• 1 u: đổi đỉnh ~u~ sang Đen; nếu đã Đen thì giữ nguyên.
• 2 K x1 x2 ... xK: với tập ~S~ gồm các đỉnh được cho, tính ~P(S) = ∑_{v ∈ S} W[v] × dist(v, closest\_black(v))~, trong đó ~closest\_black(v)~ là một đỉnh Đen gần ~v~ nhất trên toàn cây.

Nếu chưa có đỉnh Đen nào tại thời điểm truy vấn loại 2, in ~-1~. Khoảng cách là số cạnh trên đường đi ngắn nhất. Kết quả không lấy modulo.

Dữ liệu vào

• Dòng đầu chứa số nguyên ~N~ (~1 ≤ N ≤ 200000~).
• Dòng thứ hai chứa ~N~ trọng số ~W[1], …, W[N]~ (~1 ≤ W[i] ≤ 1000000~).
• ~N-1~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ mô tả một cạnh vô hướng của cây. Các đỉnh đánh số từ ~1~ đến ~N~; mỗi cạnh có độ dài ~1~.
• Dòng tiếp theo chứa số nguyên ~Q~ (~1 ≤ Q ≤ 200000~).
• Tiếp theo là ~Q~ thao tác có dạng 1 u hoặc 2 K x1 x2 ... xK như mô tả trên. Với truy vấn loại 2: ~1 ≤ K ≤ N~, các đỉnh trong tập phân biệt và thuộc ~[1,N]~.

Kết quả

Với mỗi truy vấn loại 2, in ~P(S)~, hoặc ~-1~ nếu toàn bộ cây chưa có đỉnh Đen.

Ví dụ

Input

5
2 4 1 3 5
1 2
1 3
1 4
1 5
3
1 4
2 2 3 5
2 1 2

Output

12
8

Ràng buộc

• Subtask 1: ~N, Q ≤ 2000~.
• Subtask 2: ~N, Q ≤ 200000~, không có thao tác loại 1. Theo trạng thái ban đầu, mọi kết quả trong nhóm này đều là ~-1~.
• Subtask 3: ~∑K ≤ 200000~ trên các truy vấn loại 2, đầy đủ các thao tác.

Quy cách chấm

Đọc từ đầu vào chuẩn, ghi ra đầu ra chuẩn. Có 50 test độc lập, mỗi test 2 điểm; tổng điểm là 100. Không chấm theo batch. Thời gian: 3 giây; bộ nhớ: 512 MiB.

Nguồn: Lưu Hải Phong — hpcode.edu.vn.