{"code":"nhiphan","name":"Xâu nhị phân","description":"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$.\r\n\r\nTrong tập hợp trên, ta có:\r\n- Xâu nhị phân $100$: ở vị trí số $5$.\r\n- Vị trí số $7$ trong tập là xâu nhị phân: $110$.\r\n\r\n**Yêu cầu**: Với một số $N (N \\le 63)$ cho trước, hãy 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$ ($1 \\le 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ứa 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

Output

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

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 3\r\n 100\r\n 7\t\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n 5\r\n 110\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}}