二進数の加算

文字列として与えられた2つの二進数があり、その和を二進数表現で出力するプログラムを作成する問題です。

入力

最初の行に最初の二進数文字列 a (1 ≤ |a| ≤ 10,000) が与えられます。

2行目に2つ目の二進数文字列 b (1 ≤ |b| ≤ 10,000) が与えられます。

出力

2つの二進数 a + b の合計を、二進数文字列として出力してください。

例

二進数加算のチュートリアル

十進数の足し算と同じように、二進数でも加算を行うことができます。二進数の足し算は、扱う数字が 0 と 1 しかない分、逆にシンプルです。押さえるべき基本的なルールは4つだけです:

1. 0 + 0 = 0

2. 1 + 0 = 1

3. 0 + 1 = 1

4. 1 + 1 = 10 (いわゆる 1 を繰り上げて 0 を書くイメージです)

二進数加算の例

次の例では、101 と 110 を足し算する方法を示します:

←←←←    計算は右端の桁から行います
  101
+ 110
------
 1011

これは十進数換算でいう 5 + 6 = 11 に相当し、二進数では 1011 となります。右端から順番に計算すると:

• 1 + 0 = 1

• 0 + 1 = 1

• 1 + 1 = 10 (0 を書いて 1 を繰り上げ)

• 最も左の桁に繰り上げた 1 を加えます。