You are given a string s consisting of the characters 0, 1 and/or ?. Let's call it a pattern. Let's say that the binary string (a string where each character is either 0 or 1) matches the pattern if you can replace each character ? with 0 or 1 (for each character, the choice is independent) so that the strings become equal. For example, 0010 matches ?01?, but 010 doesn't match 1??, ??, or ????. Let's define the cost of the binary string as the minimum number of operations of the form "reverse an arbitrary contiguous substring of the string" required to sort the string in non-descending order. You have to find a binary string with the minimum possible cost among those that match the given pattern. If there are multiple answers, print any of them. Input The first line contains a single integer t (1≤t≤3⋅104 ) — the number of test cases. The first and only line of each test case contains the string s (1≤|s|≤3⋅105 ) consisting of characters 0, 1, and/or ?. The sum of the string lengths over all test cases does not exceed 3⋅105 . Output For each test case, print a binary string with the minimum possible cost among those that match the given pattern. If there are multiple answers, print any of them. Example

这是一道编程题，需要你编写程序来解决。以下是C++的代码实现，可以供参考：

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while (t--) {
        string s;
        cin >> s;
        int n = s.size();
        vector<int> q;
        for (int i = 0; i < n; i++) {
            if (s[i] == '?') {
                q.push_back(i);
            }
        }
        if (q.empty()) {
            int cnt = 0;
            for (int i = 1; i < n; i++) {
                if (s[i] != s[i-1]) {
                    cnt++;
                }
            }
            if (cnt == 0) {
                cout << s << endl;
            } else if (cnt == 1) {
                cout << s << endl;
            } else {
                cout << "NO" << endl;
            }
            continue;
        }
        bool ok = false;
        string ans(n, '0');
        for (int i = 0; i < (1<<q.size()); i++) {
            for (int j = 0; j < q.size(); j++) {
                ans[q[j]] = (i>>j)&1 ? '1' : '0';
            }
            int cnt = 0;
            for (int j = 1; j < n; j++) {
                if (ans[j] != ans[j-1]) {
                    cnt++;
                }
            }
            if (cnt == q.size() || cnt == q.size()+1) {
                ok = true;
                break;
            }
        }
        if (ok) {
            cout << ans << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

该代码先处理出原始字符串中所有的问号的位置，然后枚举所有可能的填充方案，对于每个方案，计算出填充后的字符串的最小排序代价，判断是否符合要求，如果符合，则输出该方案，否则输出NO。