#include "paint.h"
//#include "grader.cpp"
#include <vector>
#include <cstdlib>
#include <iostream>
using namespace std;
const int MAXK = 105;
const int MAXN = 2e5 + 5;
int n, k;
int pref[MAXN][3];
bool canBlack[MAXN];
bool dp1[MAXN][MAXK], dp2[MAXN][MAXK];
int convertSymbol(char c)
{
if(c=='_') return 0;
if(c=='X') return 1;
if(c=='.') return 2;
}
int getSymbols(int l, int r, int c)
{
l--;r--;
if(l==-1 || l>r || l>=n) return 0;
if(l==0) return pref[r][c];
return pref[r][c] - pref[l-1][c];
}
void init(string &s, vector <int> &c)
{
n = s.size();
k = c.size() - 1;
for(int i = 0;i<=n+3;i++)
{
canBlack[i] = false;
pref[i][0] = pref[i][1] = pref[i][2] = 0;
for(int j = 0;j<=k+3;j++) dp1[i][j] = dp2[i][j] = false;
}
pref[0][convertSymbol(s[0])]++;
for(int i = 1;i<n;i++)
{
pref[i][0] = pref[i-1][0];
pref[i][1] = pref[i-1][1];
pref[i][2] = pref[i-1][2];
pref[i][convertSymbol(s[i])]++;
}
}
void fillDp1(string &s, vector <int> &c)
{
for(int i = 1;i<=n;i++)
{
if(i<c[1]) continue;
if(getSymbols(i-c[1]+1, i, 0)==0 && getSymbols(1, i-c[1], 1)==0) dp1[i][1] = true;
if(getSymbols(i, i, 1)==0) dp1[i][1] |= dp1[i-1][1];
}
for(int i = 1;i<=n;i++)
{
for(int j = 2;j<=k;j++)
{
if(c[j]+1>=i) continue;
if(getSymbols(i, i, 1)==0) dp1[i][j] |= dp1[i-1][j];
if(getSymbols(i+1, i+1, 1)==0 && getSymbols(i-c[j]+1, i, 0)==0 && getSymbols(i-c[j], i-c[j], 1)==0)
{
dp1[i][j] |= dp1[ i - c[j] - 1 ][j-1];
}
}
}
}
void markBlack(int l, int r)
{
for(int i = l;i<=r;i++) canBlack[i] = true;
}
void fillDp2(string &s, vector <int> &c)
{
for(int i = n;i>=1;i--)
{
if(n-i+1<c[k]) continue;
if(getSymbols(i, i+c[k]-1, 0)==0 && getSymbols(i+c[k], n, 1)==0)
{
dp2[i][k] = true;
if(k==1)
{
if(getSymbols(1, i-1, 1)==0) markBlack(i, i+c[k]-1);
}
else
{
if(i>2 && getSymbols(i-1, i-1, 1)==0 && dp1[i-2][k-1]==true) markBlack(i, i+c[k]-1);
}
}
if(getSymbols(i, i, 1)==0) dp2[i][k] |= dp2[i+1][k];
}
for(int i = n;i>=1;i--)
{
for(int j = k-1;j>=1;j--)
{
if(c[j]+1>=n-i+1) continue;
if(getSymbols(i, i, 1)==0) dp2[i][j] |= dp2[i+1][j];
if(getSymbols(i-1, i-1, 1)==0 && getSymbols(i, i+c[j]-1, 0)==0 && getSymbols(i+c[j], i+c[j], 1)==0)
{
dp2[i][j] |= dp2[ i + c[j] + 1 ][j+1];
if(dp2[ i + c[j] + 1 ][j+1]==true)
{
if(j==1)
{
if(getSymbols(1, i-1, 1)==0) markBlack(i, i+c[j]-1);
}
else
{
if(i>2 && getSymbols(i-1, i-1, 1)==0 && dp1[i-2][j-1]==true) markBlack(i, i+c[j]-1);
}
}
}
}
}
}
bool completeString(string &s, vector <int> &c)
{
init(s, c);
fillDp1(s, c);
fillDp2(s, c);
/*
for(int j = 1;j<k;j++)
{
for(int i = 1;i<=n-2;i++)
{
if(dp1[i][j]==true && getSymbols(i+1, i+1, 1)==0 && dp2[i+2][j+1]==true)
{
for(int p = i-c[j]+1;p<=i;p++) canBlack[p] = true;
}
}
}
for(int i = 1;i<=n;i++)
{
if(dp1[i][k]==true && getSymbols(i+1, n, 1)==0)
{
for(int p = i-c[k]+1;p<=i;p++) canBlack[p] = true;
}
}
*/
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=k;j++)
{
//cout << "dp[" << i << "][" << j << "] = " << dp[i][j] << '\n';
}
//cout << '\n';
}
if(dp2[1][1]==1) return true;
return false;
}
bool checkWhite(int ind)
{
if(ind!=n && dp2[ind+1][1]==true && getSymbols(1, ind, 1)==0) return true;
if(ind!=1 && dp1[ind-1][k]==true && getSymbols(ind, n, 1)==0) return true;
if(ind!=1 && ind!=n)
{
for(int j = 2;j<=k;j++)
{
if(dp1[ind-1][j-1]==true && dp2[ind+1][j]==true) return true;
}
}
return false;
}
bool checkBlack(int ind, vector <int> &c)
{
return canBlack[ind];
}
string solve_puzzle(string s, vector<int> c)
{
c.insert(c.begin(), -1);
string answer;
for(int i = 1;i<=s.size();i++) answer += "?";
completeString(s, c);
for(int i = 0;i<s.size();i++)
{
if(s[i]!='.')
{
answer[i] = s[i];
continue;
}
bool white = false;
if(checkWhite(i+1)==true) white = true;
bool black = false;
if(checkBlack(i+1, c)==true) black = true;
if(white!=black)
{
if(white==true) answer[i] = '_';
else if(black==true) answer[i] = 'X';
}
}
return answer;
}
/*
..........
2
3 4
.X........
1
3
........
2
3 4
..._._....
1
3
X_X_X_X
2
1 1
*/
