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

Input

• 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\).

Output

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

Example

5
00001
3   

2
00010