题目描述

0, 1, ? からなる文字列 $S$ および整数 $N$ が与えられます。 $S$ に含まれる ? をそれぞれ 0 または 1 に置き換えて $2$ 進整数とみなしたときに得られる値の集合を $T$ とします。 たとえば、$S=$ ?0? のとき、 $ T=\lbrace\ 000_{(2)},001_{(2)},100_{(2)},101_{(2)}\rbrace=\lbrace\ 0,1,4,5\rbrace $ です。

$T$ に含まれる $N$ 以下の値のうち最大のものを ($10$ 進整数として) 出力してください。 $N$ 以下の値が $T$ に含まれない場合は、代わりに -1 を出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$S$ $N$

输出格式

答えを出力せよ。

题目大意

题意简述

给定整数 $N(1\le N\le 10^{18})$ 和只包含字符 0、1、? 的字符串 $S(1\le |S|\le 60)$。

将 $S$ 视为一个二进制数，令 $T$ 为将 $S$ 中的 ? 替换为 0 或 1 后所能得到的数字集合。请求出 $T$ 中小于等于 $N$ 的最大数字，并以十进制方式输出。

如果 $T$ 中不包含小于等于 $N$ 的数字，输出 -1。

Translate by

?0?
2

1

101
4

-1

?0?
1000000000000000000

5

提示

制約

• $S$ は 0, 1, ? からなる文字列
• $S$ の長さは $1$ 以上 $60$ 以下
• $1\leq\ N\ \leq\ 10^{18}$
• $N$ は整数

Sample Explanation 1

問題文中で例示したとおり、$T=\lbrace\ 0,1,4,5\rbrace$ です。 $T$ に含まれる $N$ 以下の値は $0$ と $1$ なので、そのうちの最大である $1$ を出力します。

Sample Explanation 2

$T=\lbrace\ 5\rbrace$ であるため、$N$ 以下の値は $T$ に含まれません。