Cho tập hợp tất cả các xâu nhị phân có độ dài \(N\) được sắp xếp theo thứ tự từ điển. Ví dụ N = \(3\) ta có tập hợp: \(000\), \(001\), \(010\), \(011\), \(100\), \(101\), \(110\), \(111\).

Trong tập hợp trên, ta có:

• Xâu nhị phân \(100\): ở vị trí số \(5\).
• Vị trí số \(7\) trong tập là xâu nhị phân: \(110\).

Yêu cầu

Với một số \(N\) \((N \le 63)\) cho trước, hãy 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 \((1 \le 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

• Dòng đầu tiên chứa một số nguyên là vị trí của \(S\) trong tập hợp.
• Dòng thứ hai ghi xâu nhị phân có \(N\) phần tử nằm ở vị trí thứ \(K\).

Input 1

3
100
7

Output 1

5
110