Cho một chuỗi bit có độ dài \(n\). Với mỗi \(k\) từ \(0 ... n\), tính số chuỗi không rỗng có chứa đúng \(k\) số \(1\).

Ví dụ, nếu chuỗi là 101, có:

• \(1\) chuỗi con chứa \(0\) số \(1\): 0
• \(4\) chuỗi con chứa \(1\) số \(1\): 01, 1, 1, 10
• \(1\) chuỗi con chứa \(2\) số \(1\): 101
• \(0\) chuỗi con chứa \(3\) số \(1\)

Input

• Dòng duy nhất chứa chuỗi nhị phân độ dài \(n\).

Output

• Một dòng chứa \(n + 1\) giá trị được chỉ định trên đề bài.

Constraints

• \(1\leq n \leq 2 ⋅ 10^5\)

Example

Sample input

101

1 4 1 0