Dãy đèn tiết kiệm - Liệt kê các cách hợp lệ

Trên một hàng rào có n bóng đèn xếp thành một hàng. Mỗi bóng đèn có một trong hai trạng thái: tắt (kí hiệu 0) hoặc bật (kí hiệu 1). Mỗi cách bật/tắt được biểu diễn bởi một xâu gồm n kí tự 0 và 1.

Một cách bật/tắt được gọi là hợp lệ nếu không có hai bóng đèn liền kề cùng bật, tức là không xuất hiện hai kí tự 1 đứng cạnh nhau.

Yêu cầu

Hãy in tất cả các cách hợp lệ theo thứ tự từ điển: so sánh từ trái sang phải, 0 đứng trước 1. Chương trình phải sử dụng hàm đệ quy.

Input

Một dòng duy nhất chứa số nguyên n.

Output

Mỗi dòng là một xâu 0/1 độ dài n, tương ứng với một cách hợp lệ. Phải in đủ các cách, không thừa, không trùng và đúng thứ tự từ điển.

Ràng buộc

• 1 ≤ n ≤ 10.

Ví dụ 1

Input

4

Output

0000
0001
0010
0100
0101
1000
1001
1010

Ví dụ 2

Input

2

Output

00
01
10