{"code":"nhiphan2","name":"Xâu nhị phân 2","description":"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.\r\n\r\n**Yêu cầu**: Cho một số nguyên $N$ ($N < 63$) cho biết:\r\n- Xâu nhị phân $S$ (có độ dài $N$) nằm ở vị trí nào của tập.\r\n- Vị trí thứ $K$ ($K \\le 10^{18}$) là xâu nhị phân nào?\r\n\r\n

Input

\r\n\r\n- Dòng đầu chứa một số nguyên $N$, là độ dài của các xâu nhị phân.\r\n- Dòng thứ hai chứ một xâu nhị phân $S$ có độ dài bằng $N$.\r\n- Dòng thứ ba chứa một số nguyên $K$.\r\n\r\n\r\n

Output

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

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 5\r\n 00001\r\n 3\t\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 2\r\n 00010\r\n ```","points":300.0,"partial":true,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}