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 \lt 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 \le 10^{18})\) là xâu nhị phân nào?

Dữ liệu vào

• 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 trên từng dòng là kết quả từng yêu cầu của bài toán.

Input 1

5
00001
3

Output 1

2
00010