#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
typedef int INT;
#define pb push_back
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define fst first
#define snd second
#define int long long
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long long ll;
const ll INF = 1e15;
int N, K;
vector<INT> C;
string S;
vi prefix, bprefix;
int dp[200100][110];
vi bp, wp;
int f(int i, int j){
//cout << i << " " << j << endl;
if(i > N+1) return 0;
int &res = dp[i][j];
if(res!=-1) return res;
if(j == K) {
if(i > N+1) return 0;
if(i == N+1) return res = 1;
if(bprefix[N] - bprefix[i]) return res = 0;
wp[i]++;
return res = 1;
}
if(i >= N) return res = 0;
res = 0;
if(i + C[j] <= N and prefix[i+C[j]] - prefix[i] == 0 and S[i+C[j]] != 'X') {
res = f(i+C[j]+1, j+1);
//cout<<res<<endl;
if(res) {
wp[i+C[j]]++;
wp[i+C[j]+1]--;
bp[i]++;
bp[i+C[j]]--;
//cout << i+C[j] << endl;
}
}
if(S[i] != 'X' and f(i+1, j)){
//cout<<"White" << endl;
res = 1;
wp[i]++;
wp[i+1]--;
}
//cout << i << " " << j << " " << res << endl;
return res;
}
std::string solve_puzzle(std::string s, std::vector<INT> c) {
FOR(i, 0, 200100) FOR(j, 0, 110) dp[i][j] = -1;
S = s;
C = c;
K = c.size();
N = s.size();
S.pb('.');
prefix.assign(N+3, 0);
bprefix.assign(N+3, 0);
wp.assign(N+3, 0);
bp.assign(N+3, 0);
FOR(i, 1, N+3) prefix[i] = prefix[i-1] + (S[i-1] == '_');
FOR(i, 1, N+3) bprefix[i] = bprefix[i-1] + (S[i-1] == 'X');
f(0, 0);
FOR(i, 1, N) bp[i] += bp[i-1];
FOR(i, 1, N) wp[i] += wp[i-1];
FOR(i, 1, N) if(S[i] == 'X') wp[i] = 0;
string ret (N, '?');
FOR(i, 0, N) {
if(!wp[i]) ret[i] = 'X';
else if(!bp[i]) ret[i] = '_';
}
return ret;
}
/*
........
2 3 4
..._._....
1 3
.X........
1 3
*/
