Một cây nhị phân đầy đủ được tạo thành từ các nút được sắp xếp theo cấu trúc phân cấp. Một trong các nút là nút gốc, được coi như ở bậc 0. Nút gốc có 2 nút con, ở bậc 1. Con của mỗi nút đó ở bậc 2, v.v...

Nói chung, một cây nhị phân hoàn chỉnh ~N~ bậc bao gồm ~2^N -1~ nút, mỗi nút có 2 con, trừ nút có bậc ~L-1~.

Một số có thể được viết vào một nút. Viết các số từ 1 tới ~2^N -1~ vào một cây nhị phân hoàn chỉnh gồm ~N~ bậc sao cho nút ở bậc ~D~, giá trị tuyệt đối chênh lệch giữa tổng tất cả các nút ở cây con trái và tổng các nút ở con phả là ~2^D~.

Ví dụ, tổng các nút của cây con trái chênh tổng các nút của cây con phải là 1. Tổng của cây con trái và phải ở nút bậc 1 phải chênh nhau là 2.

Mỗi số chỉ được dùng một lần. Kết quả không cần phải là duy nhất.

Input

Một dòng duy nhất gồm số nguyên ~N~ (~1 <= N <= 15 ~), số bậc của cây.

Output

In ra ~2^N -1~ số trên một dòng, cách nhau bởi dấu cách, cây nhị phân được duyệt theo thứ tự trước (preorder traversal).

Sample Input 1

2

Sample Output 1

3 1 2

Sample Input 2

3

Sample Output 2

3 1 7 5 6 2 4