Chef challenges Akshit to solve a Challenging Problem given by him within 2 hours. Akshit accepts the challenge but after seeing the problem, he feels that it isn't his cup of tea. So, he shamelessly asks you to solve the problem for him so that he can flaunt his programming skills infront of Chef. Can you help Akshit to solve this problem but don't tell Chef that you helped Akshit ! It's a secret xD!
Formally, the problem is described below.
You are given with an integer number \(N\) in its binary representaion. A process is defined to decrease \(N\) to \(0.\) The process is described as -- Replace \(N\) with \(N \bmod \theta(N)\) were \(\theta(N)\) is the count of "ON" bits in \(N\). Say, \(N=11000111_2\), then \(\theta(N) = 5.\)
Let \(X_i\) be the binary representaion of \(N\) when its \(i-th\) bit from left is flipped. For each \(X_i (1 \leq i \leq \mid N\mid), \)calculate the number of times the process is simulated to achieve the task i.e. decrease \(X_i\) to \(0.\) See the Example below to understand better.
Consider an Example --
Say, \(N=011_2\)
- \(X_1\)(Flip \(1st\) bit from left) \(=111_2\) (\(7\) in Decimal) \(; \theta(X_1)=3\)
\(X_1= X_1 \bmod \theta(X_1)= 7 \bmod 3 = 1\) (Step \(1\))
\(X_1= X_1 \bmod \theta(X_1)= 1 \bmod 1 = 0\) (Step 2)
Total Steps for \(X_1=2\)
- \(X_2\)(Flip \(2nd\) bit from left) \(=001_2\) (\(1\) in Decimal) \(; \theta(X_2)=1\)
\(X_2= X_2 \bmod \theta(X_2)= 1 \bmod 1 = 0\) (Step 1)
Total Steps for \(X_2=1\)
- \(X_3\)(Flip \(3rd\) bit from left) \(=010_2\) (\(2\) in Decimal) \(; \theta(X_3)=1\)
\(X_3= X_3 \bmod \theta(X_3)= 2 \bmod 1 = 0\) (Step 1)
Total Steps for \(X_3=1\)
Input Format:
- The first line and the only line of the input contains a single string \(N\) (number in its binary represenentation with possibly leading zeros).
Output Format:
- Output \(\mid N\mid\) lines. Each line containing number of steps to decrease \(X_i (1 \leq i \leq \mid N\mid)\) to \(0 ;\) \((\mid N\mid = length \space of \space String \space N).\)
Constraints:
- \(1 \leq \mid N\mid \leq 2 \cdot 10^5\)
- \(\mid N\mid \) represents the length of string not the value in decimal. Say, \(N=10100\), \(\mid N\mid =5.\)
Author- Akshit Monga