$K$ が与えられます。それぞれの長さが $8848$ 以下の空でない二進文字列 $S,T$ で、異なる最長共通部分列をちょうど $K$ 個持つものを構築してください。より形式的には、$S,T$ の最長共通部分列の長さを $L$ とすると、$S,T$ の両方の部分列である長さ $L$ の異なる二進文字列がちょうど $K$ 個存在する必要があります。

この問題の制約の下では、そのような文字列が常に存在することが保証されます。

入力

入力の唯一の行には整数 $K$（$1\le K\le 10^9$）が与えられます。

出力

空でない二進文字列 $S,T$ を別々の行に出力してください。それぞれの長さは $8848$ 以下でなければなりません。長さが異なっていてもかまいません。

解が複数ある場合は、どれを出力してもかまいません。

入出力例

入力 1

1

出力 1

1111
00

入力 2

2

出力 2

10
01

入力 3

3

出力 3

010
1001

入力 4

100

出力 4

10001000001011100001010100011
11000010001010101001010011100

注記

最初の例では、1111 と 00 の最長共通部分列の長さは $0$ です。両方の部分列である長さ $0$ の文字列は空文字列の $1$ 個だけです。

第 $2$ の例では、文字列 10 と 01 の最長共通部分列の長さは $1$ です。$S,T$ の両方の部分列である長さ $1$ の文字列は 0 と 1 の $2$ 個です。

第 $2$ の例では、文字列 010 と 1001 の最長共通部分列の長さは $2$ です。$S,T$ の両方の部分列である長さ $2$ の文字列は 00、01、10 の $3$ 個です。

Everest より長い文字列を作るのは失礼でしょう……