Một tập hợp S gồm các dãy N bit 0, 1 trong đó không có hai bit 1 nào kề nhau. Ví dụ N = 5 thì S gồm các dãy 00000, 00001, 00101,… Tập S được sắp xếp theo thứ tự từ điển.

Yêu cầu: Cho một số nguyên N (N < 63) cho biết:

• Xâu nhị phân S (có độ dài N) nằm ở vị trí nào của tập.
• Vị trí thứ K (K <= 10¹⁸) là xâu nhị phân nào?

Dữ liệu vào: Cho trong file NHIPHAN2.INP:

• Dòng đầu chứa một số nguyên N, là độ dài của các xâu nhị phân.
• Dòng thứ hai chứ một xâu nhị phân S có độ dài bằng N.
• Dòng thứ ba chứa một số nguyên K.

Dữ liệu ra: In ra file NHIPHAN2.OUT:

• In trên từng dòng là kết quả từng yêu cầu của bài toán.