/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
すぬけくんは黒板に 1 以上 (2^N-1) 以下の整数をすべて書きました． ただし，整数は 2 進表記で書きました．
黒板に書かれた整数を文字列として見た時，辞書順で X 番目に小さい文字列を求めてください．
なお，入力において N は 10 進法で与えられますが，X は 2 進法で与えられます．
制約
- 1 \leq N \leq 10^6
- 1 \leq X \leq 2^N-1
- X は 2 進法で与えられる．
入力
入力は以下の形式で標準入力から与えられる．
N X
出力
答えを出力せよ．
入力例 1
3 101
出力例 1
11
黒板に書かれた文字列を辞書順に並べると，1,10,100,101,11,110,111 です．
また X=101(2\mathrm{進})=5(10\mathrm{進}) です．
よって，答えは 11 になります．
入力例 2
10 10100011
出力例 2
1001001111
入力例 3
1000000 11111
出力例 3
1000000000000000000000000000000
Score : 500 points
Problem Statement
Snuke has written on a blackboard every integer from 1 through (2^N-1), in binary.
Find the X-th lexicographically smallest string when seeing the integers on the blackboard as strings.
Here, the input gives N in decimal, but X in binary.
Constraints
- 1 \leq N \leq 10^6
- 1 \leq X \leq 2^N-1
- X is in binary.
Input
Input is given from Standard Input in the following format:
N X
Output
Print the answer.
Sample Input 1
3 101
Sample Output 1
11
The strings written on the blackboard in lexicographical order are 1, 10, 100, 101, 11, 110, 111.
Additionally, we have X=101(\mathrm{binary})=5(\mathrm{decimal}).
Thus, the answer is 11.
Sample Input 2
10 10100011
Sample Output 2
1001001111
Sample Input 3
1000000 11111
Sample Output 3
1000000000000000000000000000000