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