Contest Duration: - (local time) (120 minutes) Back to Home
C - Binary Strings /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

すぬけくんは黒板に 1 以上 (2^N-1) 以下の整数をすべて書きました． ただし，整数は 2 進表記で書きました．

なお，入力において N10 進法で与えられますが，X2 進法で与えられます．

### 制約

• 1 \leq N \leq 10^6
• 1 \leq X \leq 2^N-1
• X2 進法で与えられる．

### 入力

N
X


### 入力例 1

3
101


### 出力例 1

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


### 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