#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
const int MX=2e5+10;
int n, k;
vi c;
int sm[MX][101];
int possible[MX][101];
int smX[MX], sm_[MX];
bool visited[MX][101];
int getSum(int x, int y, char c) {
return sm[min(n,y+1)][c]-sm[x][c];
}
void addX(int x, int y) {
smX[y+1]--;
smX[x]++;
}
void add_(int x, int y) {
sm_[y+1]--;
sm_[x]++;
}
bool isPossible(int x, int y) {
if(x >= n) {
return y == k;
}
if(possible[x][y] != -1) return possible[x][y];
bool res = isPossible(x+1,y);
if(y == k) {
if(getSum(x,x,'X') == 1)
res = 0;
} else {
if(getSum(x,x+c[y]-1,'_') == 0 && getSum(x+c[y],x+c[y],'X') == 0) {
if(isPossible(x+c[y]+1,y+1))
res = 1;
} else if(getSum(x,x,'X') == 1) {
res = 0;
}
}
return possible[x][y] = res;
}
void visit(int x, int y) {
if(visited[x][y])
return;
if(x >= n) return;
visited[x][y] = 1;
if(!isPossible(x,y))
return;
if(y == k) {
add_(x,x);
visit(x+1,y);
} else {
if(getSum(x,x+c[y]-1,'_') == 0 && getSum(x+c[y],x+c[y],'X') == 0) {
if(isPossible(x+c[y]+1,y+1)) {
addX(x,x+c[y]-1);
add_(x+c[y],x+c[y]);
visit(x+c[y]+1,y+1);
}
}
if(getSum(x,x,'X') == 0 && isPossible(x+1,y)) {
add_(x,x);
visit(x+1,y);
}
}
}
string solve_puzzle(string s, vi C) {
c=C;
n = s.size(); k = c.size();
RE(i,MX) RE(j,101) sm[i][j] = 0;
RE(i,n) RE(j,101) sm[i+1][j] = sm[i][j]+(s[i]==j?1:0);
RE(i,MX) RE(j,101) possible[i][j] = -1;
RE(i,MX) smX[i]=sm_[i]=0;
RE(i,MX) RE(j,101) visited[i][j] = 0;
visit(0,0);
REP(i,1,MX) smX[i]+=smX[i-1];
REP(i,1,MX) sm_[i]+=sm_[i-1];
string ans;
RE(i,n) {
if(smX[i] && sm_[i]) {
ans.push_back('?');
} else if(smX[i]) {
ans.push_back('X');
} else {
ans.push_back('_');
}
}
return ans;
}
