CSES 2115 ↗

Bit Substrings

For each `k`, the number of non-empty substrings containing exactly `k` ones.

0
submissions
—
best score

You are given a bit string of length n. Your task is to calculate for each k between 0…n the number of non-empty substrings that contain exactly k ones.

For example, if the string is 101, there are:

  • 1 substring that contains 0 ones: 0
  • 4 substrings that contain 1 one: 01, 1, 1, 10
  • 1 substring that contains 2 ones: 101
  • 0 substrings that contain 3 ones

Input

The only input line contains a binary string of length n.

Output

Print n+1 values as specified above.

Constraints

  • 1≤n≤2⋅105

Example

Input:

101

Output:

1 4 1 0 

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/BitSubstrings/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Results

No scoring submissions yet. One counts once the kernel accepts its proof and every test passes.

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.