Background

Teacher Zhao is notorious for frequently producing broken problems. This semester he teaches Introduction to Computing.

He is well versed in The Etiquette of Bowing Out and often says: “A course exists for students to learn, not for the teacher to learn.” Following this principle, he always “takes a bow” at the end of the lesson by throwing the problems he himself does not understand at the students as homework.

This week’s homework is the reverse construction of “Global XOR Ray Tracing.” The problem was just released when a student pointed out: “Based on the properties of the problem, this is mathematically impossible to construct perfectly!” Teacher Zhao pounded the lectern and insisted, “I checked it; there absolutely is a solution!” Five minutes later, after the student reminded him, he realized his mistake.
“Oh, I got it wrong.”

To cover up his embarrassment, Teacher Zhao quickly revised the homework rules.

The “big genius” student who chose this course is busy playing Sanguosha with the newly purchased Zhou Chu hero, so now you are asked to write a program to finish this revised homework.

Description

Formally, given a 01-string $S$ of length $N$, construct an array $A$ of length $N$ consisting of positive integers that satisfies the following conditions:

• For every $1 \leq i \leq N$, $0 < A_i < 2^{60}$.
• For every $i \neq j$, $A_i \neq A_j$.

Let the global XOR sum be

$$ X = A_1 \oplus A_2 \oplus \dots \oplus A_N. $$

Define a 01-string $W$ of length $N$. For each $1 \leq i \leq N$:

• If $A_i \oplus X < A_i$, then $W_i = 1$;
• otherwise $W_i = 0$.

It is required that the Hamming distance between the string $W$ and the string $S$ does not exceed $1$, i.e.

$$ \sum_{i = 1}^{N} [W_i \neq S_i] \leq 1. $$

It suffices to output any solution satisfying the conditions. It can be proven that within the data range of this problem, such a solution always exists.

In this problem, the XOR operation is denoted by $\oplus$ and defined as follows: for two nonnegative integers $a, b$, let their binary expansions be

$$ a = \sum_{k \geq 0} a_k 2^k, \quad b = \sum_{k \geq 0} b_k 2^k, $$

where $a_k, b_k \in \{0,1\}$, and only finitely many bits are $1$. Define

$$ a \oplus b = \sum_{k \geq 0} c_k 2^k, \quad c_k = (a_k + b_k) \bmod 2. $$

That is, on each bit, if the two numbers differ, the result is $1$; if they are the same, the result is $0$. The XOR sum of several integers is computed by applying this binary operation successively; the XOR operation is associative and commutative, so the order of computation does not affect the result.

Input

The input contains a single line with a string $S$ ($1 \leq |S| \leq 10^5$), consisting only of the characters 0 and 1. Let $N = |S|$.

Output

Output one line containing $N$ space-separated positive integers, representing the array $A$ you constructed.

The output array must satisfy:

• For every $1 \leq i \leq N$, $0 < A_i < 2^{60}$.
• For every $i \neq j$, $A_i \neq A_j$.
• The string $W$ generated from $A$ as described has Hamming distance at most $1$ from the input string $S$.

If multiple valid answers exist, output any of them.

Examples

Input 1

01

Output 1

1 2

Input 2

100001

Output 2

15 86 66 69 20 68

Note

The sample outputs are not unique.

For the first sample, the output array is $[1, 2]$, and its global XOR sum is

$$ X = 1 \oplus 2 = 3. $$

Since $1 \oplus 3 = 2 > 1$, we have $W_1 = 0$; since $2 \oplus 3 = 1 < 2$, we have $W_2 = 1$. Therefore the generated string is $W = 01$, which is exactly the same as the input string.

For the second sample, the output array is

$$ [15, 86, 66, 69, 20, 68]. $$

Its global XOR sum is

$$ X = 15 \oplus 86 \oplus 66 \oplus 69 \oplus 20 \oplus 68 = 14. $$

Checking them one by one:

• $15 \oplus 14 = 1 < 15$ → $W_1 = 1$
• $86 \oplus 14 = 88 > 86$ → $W_2 = 0$
• $66 \oplus 14 = 76 > 66$ → $W_3 = 0$
• $69 \oplus 14 = 75 > 69$ → $W_4 = 0$
• $20 \oplus 14 = 26 > 20$ → $W_5 = 0$
• $68 \oplus 14 = 74 > 68$ → $W_6 = 0$

Therefore the generated string is $W = 100000$. It differs from the input string $S = 100001$ only at the sixth position, so the Hamming distance is $1$, satisfying the requirement.