Đề bài

Bạn được cung cấp một chuỗi gồm ~N~ ký tự ~0~ hoặc ~1~, được đánh số từ ~1, 2, \dots, N~. Ban đầu mỗi ký tự đại diện cho một chuỗi có độ dài một. Trong quá trình nối, hai từ ~a~ và ~b~ được chọn, xóa và được thay thế bởi chuỗi tạo ra bằng cách ghép chuỗi ~a~ đứng trước chuỗi ~b~.

Chuỗi ban đầu tạo ra ~N~ chuỗi đơn và dần được kết nối thành một chuỗi cuối cùng bằng cách sử dụng ~N - 1~ phép nối. Phép nối thứ ~i~ được mô tả bằng một cặp chỉ mục ~(a_i, b_i)~, biểu thị rằng chuỗi thứ ~a_i~ và chuỗi thứ ~b_i~ sẽ được nối với nhau. Luôn đảm bảo rằng các ký tự có chỉ số ~a_i~ và ~b_i~ không nằm trong cùng một chuỗi.

Giá trị Palindromic của một chuỗi ~w~ được định nghĩa là tổng số chuỗi con duy nhất của ~w~ là chuỗi đối xứng. Chuỗi con của một chuỗi là các chuỗi giống nhau khi đọc từ trái sang phải và phải sang trái. Chuỗi con của một chuỗi được định nghĩa là một chuỗi có được bằng cách xóa không hoặc một số ký tự khỏi đầu và cuối của chuỗi.

Đối với mỗi phép nối, hãy in ra giá trị palindromic của chuỗi kết quả.

Input

• Dòng đầu tiên chứa số nguyên ~N~ (~1 \leq N \leq 100000~), số ký tự.
• Dòng thứ hai chứa chuỗi ~N~ ký tự ~0~ và ~1~.
• ~N - 1~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_i, b_i~ (~1 \leq a_i, b_i \leq N~, ~a_i \neq b_i~) đại diện cho phép nối thứ ~i~.

Output

• In ra ~N - 1~ dòng, dòng thứ ~i~ là giá trị palindromic của chuỗi sau phép nối thứ ~i~.

Ví dụ

Sample Input 1

8
10010000
7 5
4 2
3 6
1 3
6 8
5 3
1 2

Sample Output 1

2
2
2
3
4
6
8

Giới hạn

• Thời gian: 2.0s
• Bộ nhớ: 256M

Ghi chú

• Có 30% số test với 30% số điểm của bài có ~N \leq 1000~.
• Có 30% số test khác với 30% số điểm của bài có ~a_i = 1, b_i = i + 1~ với ~i = 1, 2, \dots, N - 1~.
• Có 40% số test còn lại không có ràng buộc thêm.