Given a positive integer \(n\), list all \(2^n\) binary strings of length \(n\) in increasing lexicographic order.

Input

One line containing \(n\).

The input satisfies:

• \(1 \le n \le 16\)
• The largest output is approximately 1.1 MiB.

Output

Print 2^\(n\) lines, one binary string of length \(n\) per line. The first string is all zeroes and the last is all ones.

Example

Input

3

Output

000
001
010
011
100
101
110
111

Explanation

For n=3 there are 2^3=8 strings, listed from 000 through 111 in lexicographic order.