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ứa 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