Bessie thích xem Cowflix, và nó xem ở nhiều nơi. Nông trại của nông dân John có thể được biểu diễn như một cây \(N(1 \leq N \leq 2*10^5)\) đỉnh, và với mỗi đỉnh, Bessie sẽ xem Cowflix ở đây hoặc không. Đầu vào đảm bảo Bessie sẽ xem Cowflix ở ít nhất một đỉnh.

Thật không may, Cowflix đang giới thiệu một mô hình đăng ký mới để tránh việc chia sẻ mật khẩu. Trong mô hình mới của họ, bạn có thể chọn một vùng liên thông kích thước \(d\) trong trang trại và cần trả \(d+k\) đồng cho một tài khoản có thể sử dụng trong vùng đó. Bạn cần chọn một tập hợp các vùng liên thông phân biệt \(c_1,c_2,...,c_C\) sao cho mọi đỉnh mà Bessie xem Cowflix phải có trong một vùng nào đó. Chi phí của tập hợp trên là là \(\sum_{i=1}^{C} (|c_i|+k)\) , trong đó |\(c_i\)| là đỉnh của vùng \(c_i\). Các đỉnh mà Bessie không xem Cowflix không cần phải nằm trong các vùng trên.

Bessie lo lắng rằng mô hình đăng ký mới có thể quá đắt đối với nó và định chuyển sang Mooloo. Để giúp nó đưa ra quyết định, hãy tính số tiền tối thiểu nó cần trả cho Cowflix để duy trì việc xem phim. Vì Cowflix chưa cho biết \(k\), hãy tính kết quả cho tất cả giá trị nguyên của \(k\) từ \(1\) đến \(N\) .

Input

• Dòng đầu tiên chứa số \(N\).
• Dòng thứ hai chứa xâu nhị phân \(s_1 s_2 s_3 … s_N\), trong đó \(s_i=1\) nếu Bessie xem Cowflix tại đỉnh \(i\).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(a\) và \(b\) \((1 \leq a, b \leq N)\) biểu diễn cạnh giữa \(a\) và \(b\) trong cây.

Output

Câu trả lời cho mỗi \(k\) từ \(1\) đến \(N\) trên \(N\) dòng riêng biệt.

Scoring

• Subtask \(1\): \(N \leq 5000\)
• Subtask \(2\): Có cạnh nối giữa \(2\) đỉnh \(i\) và \(i+1\)
• Subtask \(3\): \(N \leq 10^5\)
• Subtask \(4\): Không có điều kiện gì thêm.

Example

5
10001
1 2
2 3
3 4
4 5

4
6
8
9
10

7
0001010
7 4
5 6
7 2
5 1
6 3
2 5

4
6
8
9
10
11
12