#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
array<vector<vector<int>>, 2> get(string s, vector<int> c) {
int n = s.size();
int k = c.size();
s = " " + s;
ranges::reverse(c); c.push_back(0); ranges::reverse(c);
vector<vector<int>> w(n + 1, vector<int>(k + 1));
vector<vector<int>> b(n + 1, vector<int>(k + 1));
for (int i = 0; i <= n; i++) {
w[i][0] = b[i][0] = 1;
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
if (b[i - 1][j] && s[i] != 'X') {
w[i][j] = 1;
}
if (i - c[j] >= 0 && w[i - c[j]][j - 1] && s[i - c[j]] != '_') {
b[i][j] = 1;
}
}
}
return {w, b};
}
string solve_puzzle(string s, vector<int> c) {
int n = s.size();
int k = c.size();
auto [w1, b1] = get(s, c);
ranges::reverse(s);
ranges::reverse(c);
auto [w2, b2] = get(s, c);
reverse(w2.begin() + 1, w2.end());
reverse(b2.begin() + 1, b2.end());
// for (int i = 0; i <= n; i++) {
// cout << w2[i][k] << ' ';
// }
// cout << '\n';
string ans(n, ' ');
// cout << w1[2][0] << ' ' << w2[2][2] << '\n';
for (int i = 1; i <= n; i++) {
bool white = 0, black = 0;
for (int j = 0; j <= k; j++) {
if (w1[i][j] && w2[i][k - j]) {
white = 1;
}
if (b1[i][j] && b2[i][k - j]) {
black = 1;
}
}
if (white && black) {
ans[i - 1] = '?';
} else if (white) {
ans[i - 1] = '_';
} else {
ans[i - 1] = 'X';
}
}
return ans;
}
