#include "paint.h"
#include<bits/stdc++.h>
#include <cstdlib>
using namespace std;
bool dp[200005][205];
int n, prx[200005], k, pre[200005], canx[200005], cane[200005];
set<int>pos[205];
string ans;
string solve_puzzle(string s, vector<int> c)
{
n=s.length();
k=c.size();
for(int i=0; i<n; i++)
{
if(s[i]=='X') prx[i]=1;
if(s[i]=='_') pre[i]=1;
if(i) prx[i]+=prx[i-1], pre[i]+=pre[i-1];
}
for(int i=0; i<n; i++)
{
for(int j=0; j<k; j++)
{
if((j and pos[j-1].size()==0) or i-c[j]+1<0) continue;
if(!j)
{
if(pre[i]-pre[i-c[j]]==0 and prx[i-c[j]]==0 and s[i+1]!='X')
{
dp[i][j]=1;
pos[j].insert(i);
}
continue;
}
auto it=pos[j-1].upper_bound(i-c[j]-1);
if(it==pos[j-1].begin()) continue;
--it;
if(pre[i]-pre[i-c[j]]==0 and prx[i-c[j]]-prx[*it]==0 and s[i+1]!='X')
{
if(j==k-1 and prx[n-1]-prx[i]) continue;
dp[i][j]=1;
pos[j].insert(i);
}
}
}
int last=n-1;
/*for(int i=0; i<k; i++)
{
cout<<"pos["<<i<<"] = ";
for(int u : pos[i])
cout<<u<<' ';
cout<<endl;
}*/
for(int j=k-1; j>=0; j--)
{
auto it=pos[j].begin();
cane[(*it)+1]++;
cane[last+2]--;
// cout<<"in cane : "<<(*it)+1<<' '<<last<<endl;
auto it2=pos[j].upper_bound(last);
--it2;
last=((*it2)-c[j]-1);
for(; ; --it2)
{
// (*it2)-c[j]+1 ... (*it2)
if(j!=k-1)
{
auto itplu=pos[j+1].lower_bound(*(it2)+1+c[j+1]);
if(prx[(*itplu)-c[j+1]]-prx[*it2])
{
if(it2==pos[j].begin()) break;
else continue;
}
}
canx[(*it2)-c[j]+1]++;
canx[(*it2)+1]--;
// cout<<"in canx : "<<j<<' '<<(*it2)-c[j]+1<<' '<<(*it2)<<endl;
if(it2==pos[j].begin()) break;
}
// cout<<"last "<<last<<endl;
}
if(last+2>=0) cane[0]++, cane[last+2]--;
for(int i=1; i<n; i++)
cane[i]+=cane[i-1], canx[i]+=canx[i-1];
for(int i=0; i<n; i++)
{
cout<<i<<' '<<canx[i]<<' '<<cane[i]<<endl;
if(s[i]=='.')
{
if(cane[i] and canx[i]) ans+='?';
else if(cane[i]) ans+='_';
else ans+='X';
}
else ans+=s[i];
}
return ans;
}
