Minary Encoding

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

The speed of the standard binary multiplication algorithm depends on the number of non-zero bits in the multiplier. If we introduce a `negative' bit, then strings of 2 or more `1' bits can be replaced by a `1' bit, a string of `0' bits and a `negative' bit. If we represent the `negative' bit by `#', then the string `01111' can be replaced by `1000#'. This string has only two non-zero bits as opposed to 4 in the original formulation. We call the resultant string a `minary' string.

Write a program that will read in a series of strings, in either binary or minary notation and will convert them to the other notation. Note that on input, all binary strings will start with `0', and all minary strings will start with `1'. This will not necessarily be true of the output. 

Input

 Input will consist of a series of lines, each line consisting of either a binary number (starting with `0') or a minary number (starting with `1'). The file will be terminated by a line consisting of a single #. 

Output

 Output will consist of a series of lines, one for each line of the input. Each line will consist of a converted string, that is binary numbers are represented in minary, and vice versa. 

Sample Input

01110
0111101111
100#010100#
#

Sample Output

100#0
1000#1000#
01110100111

Hint


Source