Without two consecutive ones

Given positive integer n, print all binary sequences of length n without consecutive ones, in lexicographical order.

Input

One positive integer n (n ≤ 20).

Output

Print each sequence in a separate line. Digits in a sequence must be separated with a space.

Examples