Cậu bé An yêu thích Toán học nên người thân của cậu thường tặng cậu những món đồ chơi liên quan đến dãy các con số.

Vào dịp sinh nhật năm nay, An được anh trai tặng một khối đồ chơi dài có ghi ~ n ~ số ~ 0 ~ và ~ 1 ~. Trong khi chơi An muốn chia dãy ~ n ~ số ~ 0 ~ và ~ 1 ~ trên đồ chơi thành nhiều phần, mỗi phần gồm các số liên tiếp nhau có tổng là một số lẻ, độ dài của mỗi phần tối đa là ~ m ~.

Yêu cầu: Với mỗi ~ m ~ từ ~ 1 ~ tới ~ n ~, bạn hãy giúp An tìm số phần nhỏ nhất hoặc chỉ ra là không thể chia.

Dữ liệu vào:

Dòng đầu tiên chứa số nguyên ~ n ~.

Dòng thứ hai của mỗi test chứa một xâu ~a_1 a_2 … a_n~ với ~ a_i=0 ~ hoặc ~ a_i=1 ~

Kết quả:

In ra ~ n ~ số nguyên, mỗi số cách nhau 1 dấu cách. Số nguyên thứ ~ m ~ mô tả số phần nhỏ nhất có tổng lẻ và độ dài mỗi phần tối đa là ~ m ~, hoặc ~ -1 ~ nếu không thể chia.

Ví dụ:

Input

5
01101 

Output

-1 3 3 3 1 

Giải thích

Nếu ~ m = 1 ~, không có cách chia nào hợp lệ, bởi phần đầu tiên chỉ chứa một số ~ 0 ~.

Với ~ m = 2, 3, 4 ~, chúng ta có thể chia nó thành ~ 01|10|1 ~. Chú ý rằng ~ 01|1|01 ~ cũng là một cách chia thỏa mãn.

Nếu ~ m = 5 ~, cách chia thành duy nhất một phần ~ 01101 ~thỏa mãn bởi tổng 3 là số lẻ.

Giới hạn:

Subtask 1: 20% tổng số test có ~ n ~ ~ ≤ ~ 100.

Subtask 2: 15% tổng số test có ~ n ~ ~ ≤ ~ 600.

Subtask 3: 15% tổng số test có ~ n ~ ~ ≤ ~ 1000.

Subtask 4: 20% tổng số test có ~ n ~ ~ ≤ ~ 7000.

Subtask 5: 15% tổng số test có ~ n ~ ~ ≤ ~ 10000.

Subtask 6: 15% các test có ~ 1 ≤ n ≤2×10^5 ~