#include "paint.h"
#include <cstdlib>
#include <bits/stdc++.h>
using namespace std;
const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef long double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxn 200020
ii n, k, a[maxn], b[maxn], dp1[maxn][110][2], dp2[maxn][110][2];
ii ansb[maxn], answ[maxn], ps[maxn], qtdw[maxn];
string ans;
//0->.
//1->_
//2->X
std::string solve_puzzle(std::string s, std::vector<int> c) {
//begin
n = s.size();
k = c.size();
for(ii i = 1; i <= n; i++) {
qtdw[i] = qtdw[i-1];
if(s[i-1] == '.') a[i] = 0;
else if(s[i-1] == '_') {
qtdw[i]++;
a[i] = 1;
}
else a[i] = 2;
}
for(ii i = 1; i <= k; i++) {
b[i] = c[i-1];
}
for(ii i = 0; i <= n; i++) {
for(ii j = 0; j <= k; j++) {
for(ii ant = 0; ant <= 1; ant++) {
if(i == 0 && j == 0) {
dp1[i][j][ant] = 1;
continue;
}
ii ans = 0;
//if can be white:
if(i != 0 && a[i] != 2) ans = max(ans, dp1[i-1][j][0]);
//if can be black:
if(j != 0 && ant == 0 && i-b[j]+1 >= 1 && qtdw[i] - qtdw[i-b[j]] == 0) ans = max(ans, dp1[i-b[j]][j-1][1]);
dp1[i][j][ant] = ans;
}
}
}
for(ii i = n+1; i >= 1; i--) {
for(ii j = k+1; j >= 1; j--) {
for(ii ant = 0; ant <= 1; ant++) {
if(i == n+1 && j == k+1) {
dp2[i][j][ant] = 1;
continue;
}
ii ans = 0;
//if can be white:
if(i != n+1 && a[i] != 2) ans = max(ans, dp2[i+1][j][0]);
//if can be black:
if(j != k+1 && ant == 0 && i+b[j]-1 <= n && qtdw[i+b[j]-1] - qtdw[i-1] == 0) ans = max(ans, dp2[i+b[j]][j+1][1]);
dp2[i][j][ant] = ans;
}
}
}
for(ii i = 1; i <= n; i++) {
for(ii j = 1; j <= k+1; j++) {
//i is white
if(a[i] != 2) answ[i] = max(answ[i], (dp1[i-1][j-1][0]&dp2[i+1][j][0]) );
}
for(ii j = 1; j <= k; j++) {
//interval (i,i+b[j]-1) black
if(i+b[j]-1 <= n && (dp1[i-1][j-1][1]&dp2[i+b[j]][j+1][1]) == 1 && qtdw[i+b[j]-1]-qtdw[i-1] == 0) {
ps[i]++;
ps[i+b[j]]--;
}
}
ps[i]+= ps[i-1];
if(ps[i] >= 1) ansb[i] = 1;
if(answ[i] == 1 && ansb[i] == 1)
ans+= '?';
else if(answ[i] == 1)
ans+= '_';
else if(ansb[i] == 1)
ans+= 'X';
}
return ans;
}
