NTSHEEP - SHEEP

• Thời gian: 0.123s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

Ngày đẹp trời nọ, đàn cừu trắng rủ nhau đi chơi. Chúng đi đến một chiếc cầu thì gặp một đàn cừu đen cũng đang dẫn nhau đi chơi. :D.

Chiếc cầu có độ dài 2*N+1. Mỗi đàn cừu đều có N con, mỗi con chiếm hết một đơn vị độ dài trên cầu. Hai đàn cừu đứng ở 2 đầu cầu, vì thế chỉ trống 1 ô duy nhất ở giữa cầu. Các con cừu đều hiếu chiến, không chịu lùi và chỉ muốn tiến. Vì thế muốn đi lên phía trước chỉ có thể đi vào ô trống, hoặc nhảy qua các con cừu khác để đến ô trống. Tuy vậy sức các con cừu có hạn, chỉ nhảy qua được tối đa 1 con cừu khác mà thôi.

Các con cừu không thông minh cho lắm nên không tìm được cách đi qua cầu. May mắn thay, đúng lúc đó LC đi thuyền ngang qua, các con cừu vội hỏi LC. Nhưng LC cũng bí, do không đem theo laptop theo :D. Hãy giúp LC chỉ cho các con cừu 1 cách đi tối ưu nhất.

Ví dụ: Với n=1, B mô tả đàn cừu đen, W mô tả đàn cừu trắng. Một trong các cách di chuyển tối ưu là:

W B
 WB
BW 
B W

Input

• Gồm một số nguyên N duy nhất (1≤N≤12)

Output

• Gồm 1 dòng duy nhất ghi dãy số a với ý nghĩa tại bước thứ i thì con cừu đứng ở vị trí a[i] trên cầu cần di chuyển. Nếu có nhiều đáp án, in ra đáp án với thứ tự từ điển nhỏ nhất.

Example

Input:
1

Output:
1 3 2

• Người up: iamtnl
• Nguồn bài: Base on USACO Training