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