Cho một số nguyên dương ~N~. Hãy sinh ra ~N~ số nhị phân đầu tiên (bắt đầu từ số 1).

Gợi ý: Hãy sử dụng cấu trúc dữ liệu Hàng đợi (Queue) để sinh các số nhị phân tiếp theo bằng cách nối thêm 0 và 1 vào sau các số nhị phân đã sinh ra trước đó.

Dữ liệu

Gồm một dòng duy nhất chứa số nguyên dương ~N~ (~1 \le N \le 10^4~).

Kết quả

In ra một dòng duy nhất chứa ~N~ số nhị phân đầu tiên. Các số được phân cách nhau bởi một khoảng trắng.

Ví dụ

Input 1

5

Output 1

1 10 11 100 101

Input 2

10

Output 2

1 10 11 100 101 110 111 1000 1001 1010