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?

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

Output

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

Example

3
100
7   

5
110