Hệ nhị phân (hay hệ đếm cơ số 2) là một hệ đếm dùng 2 ký tự để biểu đạt một giá trị số, bằng tổng số các lũy thừa của 2. Người ta thường sử dụng 2 ký tự đó 0 và 1. Trong bài toán này khi liệt kê ra dãy nhị phân Mr Toàn muốn bạn hiểu rõ hơn quy trình đệ quy sinh ra các dãy đó nên hạn chế số lượng dãy nhị phân in ra. Cụ thể Mr Toàn muốn bạn hãy liệt kê tất cả các dãy nhị phân độ dài đúng \(n\) thoả mãn điều kiện cụm “01” không xuất hiện trong dãy nhị phân này.

Yêu cầu:

Hãy liệt kê tất cả các dãy nhị phân độ dài đúng \(n\) thoả mãn điều kiện cụm “01” không xuất hiện theo thứ tự từ điển tăng dần.

Dữ liệu vào Specification

• Gồm 1 dòng là số nguyên \(n\) \((0<n \le 20)\).

Dữ liệu ra Specification

• Tất cả các dãy nhị phân độ dài \(n\) thoả mãn điều kiện cụm “01” không xuất hiện theo thứ tự từ điển tăng dần.

Sample Input

3

Sample Output

000
100
110
111