問題文

正整数 N が与えられる．

正整数 m に対して，美しい模様とは，m 行 N 列のマス目の各マスに文字 0, 1 のいずれかを以下の条件を満たすように書き込んだものとする：

• どの 2 つの行についても，文字が異なる列が 1 箇所以上ある．
• 各 i = 1, 2, \ldots, m-1 について，i 行目と i+1 行目で文字が異なる列はちょうど 1 箇所である．
• 1 と 1 は横に隣接しない．

美しい模様が存在するような最大の m を求め，さらにその m に対する美しい模様を 1 つ求めよ．

制約

• 美しい模様が存在するような最大の m は，mN \le 10^7 を満たす．

入力例 1

2

出力例 1

3
10
00
01

この出力例のほかに，

3
01
00
10

も正しい出力である．