当前没有测试数据。

D - 位掩码

得分: 400 分

问题描述

给定整数 $N$ 和一个由 0、1 和 ? 构成的字符串 $S$。

设 $T$ 是将 $S$ 中的每个 ? 替换为 0 或 1 并将结果解释为二进制整数得到的值的集合。

例如，如果 $S = ?0?$，则得到 $T=\lbrace 000_{(2)},001_{(2)},100_{(2)},101_{(2)}\rbrace=\lbrace 0,1,4,5\rbrace$。

请将 $T$ 中不大于 $N$ 的最大值以十进制整数形式打印出来。

如果 $T$ 中不存在不大于 $N$ 的值，则打印 -1。

约束条件

• $S$ 是由 0、1 和 ? 构成的字符串。
• $S$ 的长度在1到60之间。
• $1\leq N \leq 10^{18}$
• $N$ 是一个整数。

输入

输入以以下格式从标准输入给出。

$S$

$N$

输出

输出答案。

样例输入1

?0?

2

样例输出1

1

根据问题描述，$T=\lbrace 0,1,4,5\rbrace$。其中，0 和 1 都小于等于 $N$，所以你应该打印其中最大的数，即 1。

样例输入2

101

4

样例输出2

-1

我们得到 $T=\lbrace 5\rbrace$，其中不包含任何小于等于 $N$ 的值。

样例输入3

?0?

1000000000000000000

样例输出3

5