Giải bài trực tuyến

Hôm nay, Pirate sẽ truyền dạy một kinh nghiệm quý báu cho các anh chàng có nhiều bạn gái...

Tất nhiên là việc lưu số điện thoại vào danh bạ có nhiều lợi ích, nhưng khi bạn gái trả bài: "Anh có nhớ số em không?", trong thâm tâm các nàng luôn muốn câu trả lời bạn là "Anh chỉ nhớ mỗi số em thôi!". Khi số lượng bạn gái tăng lên cũng đồng nghĩa với số lượng số điện thoại bạn cần phải ghi nhớ cũng tăng lên một cách chóng mặt, nhất là với các nàng thích xài SIM khuyến mãi.

Một sự cố thường gặp nhất đó là bạn nhầm số của bé X sang bé Y. Thế là bé X móc ngay điện thoại ra bấm số và có một cuộc "nội chiến" xảy ra. 

Vậy làm sao để ghi nhớ các số điện thoại một cách nhanh chóng và an toàn? 

Pirate đã nghĩ ra một quy trình mã hóa số điện thoại như sau:

• Giả sử số điện thoại của bạn được biểu diễn bằng dãy số a₁, a₂,..., a_N (0 ≤ a_i ≤ 9 với 1 ≤ i ≤ N).
• Đặt s₁ = a₁, s_i = s_{i - 1} + a_i (với 1 < i ≤ N).
• Tìm số thứ tự từ điển của dãy {s_N} trong tập các dãy được sinh ra từ tất cả các số điện thoại theo nguyên tắc trên. Trừ số đó đi một đơn vị.
• Trong dãy số N bit biểu diễn nhị phân của số vừa nhận được, gọi K là dãy bit 0 liên tiếp nhau dài nhất. Tìm thứ tự từ điển của dãy N bit trên trong tập các dãy nhị phân N bit có không quá K bit 0 liên tiếp, gọi số đó là X.

Nhiệm vụ của bạn là giúp Pirate viết một chương trình giúp tìm ra một số điện thoại nếu biết được N, X và K.

Lưu ý: dãy số {a_N} được gọi là lớn hơn dãy số {b_N} khi và chỉ khi tồn tại một chỉ số i sao cho a_j = b_j (với mọi 1 ≤ j < i) và a_i > b_i. Trong một tập hợp các dãy số có cùng tính chất nào đó, thứ tự từ điển của một dãy số là số lượng dãy số trong tập không lớn nó (bao gồm cả chính nó).

Input

• Ghi ba số nguyên N, X và K.

Output

• Gồm một dòng duy nhất ghi ra dãy số {a_N} ban đầu, các số cách nhau bởi dấu cách.

Giới hạn

• 1 ≤ N, K ≤ 30; 1 ≤ X ≤ 10⁹.
• 30% số test có 1 ≤ N, K ≤ 10.
• Dữ liệu vào đảm bảo có kết quả.

Example

Input:
4 3 2

Output:
0 0 0 4

Giải thích: dãy nhị phân 4 bit thứ 3 có không quá 2 bit 0 liên tiếp là 0100. Đây là biểu diễn của số 4. Từ đó suy ra được dãy {s_N} là (0, 0, 0, 4). Vậy dãy {a_N} là (0, 0, 0, 4).

Input:
4 5 1

Output:
0 0 1 1

Giải thích: dãy nhị phân 4 bit thứ 5 có không quá 1 bit 0 liên tiếp là 1011. Đây là biểu diễn của số 11. Từ đó suy ra được dãy {s_N} là (0, 0, 1, 2). Vậy dãy {a_N} là (0, 0, 1, 1).