Fibonacci Representation Multiplication

We define the Fibonacci sequence as \(F_1=1,\; F_2=2,\; F_i=F_{i-1}+F_{i-2}\) for \(i\ge3\). For any positive integer \(x\), there is a unique Fibonacci representation \((b_1,b_2,\dots,b_n)\) satisfying:

1. \(b_1\times F_1+b_2\times F_2+\cdots+b_n\times F_n=x\).
2. For \(1\le i<n\), we have \(b_i\in\{0,1\}\) and \(b_n=1\).
3. For \(1\le i<n\), \(b_i\times b_{i+1}=0\) (i.e. no two consecutive ones).

For example:

• \(2=(0,1)\) because \(0\times F_1+1\times F_2=2\).
• \(4=(1,0,1)\) since \(1\times F_1+0\times F_2+1\times F_3=1+3=4\).
• \(5=(0,0,0,1)\) as \(F_4=5\).
• \(20=(0,1,0,1,0,1)\) because \(F_2+F_4+F_6=2+5+13=20\).

Given the Fibonacci representations of two positive integers \(A\) and \(B\) (each provided as a string of binary digits where the first digit corresponds to \(b_1\) and the last digit is always 1), compute and output the Fibonacci representation of \(A \times B\) using the same format. If necessary, omit extra high-order zeros while ensuring the last digit is 1.

inputFormat

The input consists of two lines. Each line is a non-empty string of characters '0' or '1' representing the Fibonacci representation of a positive integer. The first character denotes (b_1) (coefficient of (F_1)) and the last character is always '1'.

outputFormat

Output a single line containing the Fibonacci representation (a string of '0' and '1' digits) of the product (A \times B), in order from (F_1) to (F_n) with no unnecessary high-order zeros, and the representation must end with '1'.

sample

01
101

00001