#include "paint.h"
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<int> G(2e5);
string solve_puzzle(string s, vector<int> c)
{
//THE STRING IS ONE-INDEXED, THE BLOCKS ARE ZERO-INDEXED
int n = s.size();
s = "!" + s;
vector<int> blacksum(n+1);
blacksum[0] = 0;
for(int i = 1; i <= n; i++) blacksum[i] = blacksum[i-1] + (s[i] == 'X');
vector<int> whitesum(n+1);
whitesum[0] = 0;
for(int i = 1; i <= n; i++) whitesum[i] = whitesum[i-1] + (s[i] == '_');
vector<int> psblwhite(n+1, 0);
vector<int> psblblack(n+1, 0);
int k = c.size();
vector<int> pos(k); //rightmost position of the block
pos.push_back(n+1);
c.push_back(1);
for(pos[0] = c[0]; whitesum[pos[0]] - whitesum[pos[0] - c[0]] != 0; pos[0]++);
for(int j = 1; j < k; j++)
{
for(pos[j] = pos[j-1] + c[j] + 1; whitesum[pos[j]] - whitesum[pos[j] - c[j]] != 0; pos[j]++);
}
for(int j = k-1; j >= 0; j--)
{
while(whitesum[pos[j]] - whitesum[pos[j] - c[j]] != 0
|| blacksum[pos[j+1] - c[j+1]] - blacksum[pos[j]] != 0
|| s[pos[j] - c[j]] == 'X')
pos[j]++;
}
for(int i = 1; i <= pos[0] - c[0]; i++) psblwhite[i] = 1;
for(int j = 0; j < k; j++)
{
for(int i = pos[j] - c[j] + 1; i <= pos[j]; i++) psblblack[i] = 1;
for(int i = pos[j] + 1; i <= pos[j+1] - c[j+1]; i++) psblwhite[i] = 1;
}
for(int i = 1; i <= n; i++) cout << psblwhite[i];
cout << '\n';
return "?";
}
