Một xâu ký tự chỉ gồm các ký tự 0 và 1 được gọi là một xâu nhị phân.

Yêu cầu: Hãy liệt kê tất cả các xâu nhị phân độ dài ~n~ theo thứ tự từ điển.

Input

• Gồm một số nguyên dương ~n~ ~(n \le 20)~.

Output

• In ra ~2^n~ dòng, mỗi dòng là một xâu nhị phân, theo thứ tự từ điển.

Sample Input

3

Sample Output

000
001
010
011
100
101
110
111