#include <iostream>
#include <fstream>
#include <algorithm>
#include <cstring>
#include <climits>
#include <cassert>
#include <tuple>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <numeric>
using namespace std;
typedef long long LL;
typedef vector<int> Vi;
typedef vector<LL> VL;
typedef vector<bool> Vb;
typedef vector<vector<int>> Vii;
typedef vector<vector<vector<int>>> Viii;
typedef vector<vector<pair<int, int>>> Vip;
#define forR(i, n) for (int i = 0; i < (n); i++)
int dp[5003][5003];
bool has_solution(const string& _s, const Vi& c) {
int k = c.size();
int n = _s.size();
string s = "_" + _s;
memset(dp, 0, sizeof(dp));
// [i][j] : s[1 .. i] matches c[0 .. j-1]
forR(i, n + 1) {
if (s[i] == 'X')
break;
else
dp[i][0] = 1;
}
int lastWhite = 0;
for (int i = 1; i <= n; i++) {
if (s[i] == '_') lastWhite = i;
int potentialBlack = i - lastWhite;
for (int j = 1; j <= k; j++) {
if (potentialBlack >= c[j - 1] && s[i - c[j - 1]] != 'X'
&& (i + 1 > n || s[i + 1] != 'X')) {
// can choose c[j-1]
if (i - c[j - 1] - 1 < 0) {
dp[i][j] = j == 1;
} else if (dp[i - c[j - 1] - 1][j - 1]) {
dp[i][j] = 1;
}
}
if (s[i] != 'X') {
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
}
}
}
return dp[n][k];
}
string solve_puzzle(string s, Vi c) {
int n = s.size();
string s_ans = s;
for (int i = 0; i < n; i++) {
if (s[i] == '.') {
// try white
s[i] = '_';
bool white = has_solution(s, c);
// try black
s[i] = 'X';
bool black = has_solution(s, c);
s[i] = '.';
if (black && white) {
s_ans[i] = '?';
} else if (white) {
s_ans[i] = '_';
} else {
assert(black);
s_ans[i] = 'X';
}
}
}
return s_ans;
}
#ifdef TEST_LOCAL
int main() {
auto r = solve_puzzle(".................", Vi{ 2,3,6,2 });
return 0;
}
#endif
