以下、整数は \(2\) 進数表記されているものとし、一番下の位から順番に \(1\) 番目の位、\(2\) 番目の位、\(\dots\) と呼びます。 また、非負整数 \(n,i\) に対して、\(n\) の \(i\) 番目の位を \(n[i]\) と表記します。加えて、文字の 0,1 と数字の \(0,1\) を断りなく同一視します。

整数 \(t\) を一つ取ります。\(t \leq N\) であり、\(t\) と \(N\) を上の位から順番に見ていったときに初めて数字が異なるのが \(i\) 番目の位であるとします（\(t=N\) のとき \(i=-1\)）。すなわち、

• \(i\neq -1\) ならば、 \(t[i]=0\) かつ \(N[i]=1\)
• すべての \(j\ (j >i)\) に対して、 \(t[j]=N[j]\)

が満たされるとします。このとき、\(t\in T\) となるための必要十分条件は以下が全て満たされることです。

• \(i\neq -1\) ならば、 (\(s[i]=\)? または \(s[i]=\)0) かつ \(N[i]=1\)
• すべての \(j\ (j >i)\) に対して、 \(s[j]=\)? または \(s[j]=N[j]\)
• すべての \(j\ (j <i)\) に対して、 \(s[j]=\)? または \(s[j]=t[j]\)

上 \(2\) つの条件を満たす最大の \(i\) を \(i^*\) とします (これは \(S\) と \(N\) のみに依存します)。\(i\) が大きいほど \(t\) も大きくなることを考えると、\(i=i^*\) および \(3\) 番目の条件を満たす \(t\) のうち最大のものが求める答えです。よって、以下のアルゴリズムによってこの問題を解くことができます。

1. \(i^*\) を求める。ただし、上 \(2\) つの条件を満たす \(i\) が存在しない場合答えは -1。
2. \(j\ (j < i^*)\) に対して、\(s[j]=\)? ならば \(s[j]\) を 1 で置き換える。
3. \(j\ (j > i^*)\) に対して、\(s[j]=\)? ならば \(s[j]\) を \(N [j]\) で置き換える。
4. \(S\) を \(2\) 進整数とみなしたときに得られる値を出力する。

実装例 (C++) :

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    string s;
    ll n;
    cin >> s >> n;
    
    reverse(s.begin(), s.end());
    while (s.size() < 60) s.push_back('0');
    int lb = -1;
    for (int i = 0; i < 60; i++) {
        if (s[i] != '?' and s[i] - '0' != (n >> i & 1)) lb = i;
    }
    if (lb == -1) {
        cout << n << endl;
        return 0;
    }
    for (int i = lb; i < 60; i++) {
        if (s[i] == '1' or !(n >> i & 1)) continue;
        s[i] = '0';
        for (int j = 0; j < i; j++) {
            if (s[j] == '?') s[j] = '1';
        }
        for (int j = i + 1; j < 60; j++) {
            s[j] = '0' + (n >> j & 1);
        }
        ll ans = 0;
        for (int j = 59; j >= 0; j--) {
            ans *= 2;
            ans += s[j] - '0';
        }
        cout << ans << endl;
        return 0;
    }
    cout << -1 << endl;
}