#include "paint.h"
#include <bits/stdc++.h>
using namespace std;
const int MOD = (int)1e9+7,MOD2=(int)1e9+9;
typedef long long ll;
ll dp[200003][103],dp2[200003][103],cnt[200003],ans[200003][103];
string ANS;
string solve_puzzle(string s, vector<int> c) {
int n=(int)s.size(),k=(int)c.size();
for (int i = 1; i <= n; ++i)
{
if(s[i-1]=='_')cnt[i]++;
cnt[i]+=cnt[i-1];
}
dp[n+1][k+1]=dp2[0][0]=1;
for (int i = n; i >= 1; i--)
{
for (int j = 1; j <= k; ++j){
if((i+c[j-1])<=(n+1) && ((i+c[j-1])==(n+1) || s[i+c[j-1]-1]!='X') && (i==1||(s[i-2]!='X')) && !(cnt[i+c[j-1]-1]-cnt[i-1])){
if((i+c[j-1])==(n+1))dp[i][j]=(dp[i][j]+dp[i+c[j-1]][j+1])%MOD;
else dp[i][j]=(dp[i][j]+dp[i+c[j-1]+1][j+1])%MOD;
}
if(s[i-1]!='X')dp[i][j]=(dp[i][j]+dp[i+1][j])%MOD;
}
if(s[i-1]!='X')dp[i][k+1]=(dp[i][k+1]+dp[i+1][k+1])%MOD;
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= k; ++j){
if((i-c[j-1])>=0 && (!(i-c[j-1]) || s[i-c[j-1]-1]!='X') && (i==n||(s[i]!='X')) && !(cnt[i]-cnt[i-c[j-1]])){
if(!(i-c[j-1]))dp2[i][j]=(dp2[i][j]+dp2[i-c[j-1]][j-1])%MOD;
else dp2[i][j]=(dp2[i][j]+dp2[i-c[j-1]-1][j-1])%MOD;
}
if(s[i-1]!='X')dp2[i][j]=(dp2[i][j]+dp2[i-1][j])%MOD;
}
if(s[i-1]!='X')dp2[i][0]=(dp2[i][0]+dp2[i-1][0])%MOD;
}
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= k; ++j){
if((i+c[j-1])<=(n+1) && ((i==1)||s[i-2]!='X') && ((i+c[j-1])==(n+1) || s[i+c[j-1]-1]!='X') && !(cnt[i+c[j-1]-1]-cnt[i-1]))
ans[i][j]=(dp[min(n+1,i+c[j-1]+1)][j+1]*dp2[max(0,i-2)][j-1])%MOD;
ans[i][j]+=ans[i-1][j];
}
for (int i = 1; i <= n; ++i)
{
if(s[i-1]!='.')ANS.push_back(s[i-1]);
else{
ll f=0,f2=0;
for (int j = 1; j <= k; ++j){
f=(f+(ans[i][j]-ans[max(1,i-c[j-1]+1)-1][j]+MOD)%MOD)%MOD;
f2=(f2+(dp[i+1][j]*dp2[i-1][j-1])%MOD)%MOD;
}
f2=(f2+(dp[i+1][k+1]*dp2[i-1][k])%MOD)%MOD;
if(f==dp[1][1])ANS.push_back('X');
else if(f2==dp[1][1])ANS.push_back('_');
else ANS.push_back('?');
}
}
return ANS;
}
