#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
const int maxn = 102;
vector <vector <int> > v[maxn];
int dp[maxn][maxn]; // dp[i][j] -> if you can finish i-th partition on the position j
int l[maxn];
int r[maxn];
int icl[maxn];
string solve_puzzle(string s, vector<int> c) {
int n = s.size();
int k = c.size();
string rs = s;
auto safe = [&] (int x, int p) {
if (x - p + 1 < 0) return 0;
for (int i = x; i >= x - p + 1; i--) {
if (s[i] == '_') return 0;
}
return 1;
};
for (int i = 0; i < n; i++){
dp[0][i] = safe(i, c[0]);
}
for (int i = 1; i < k; i++){
for (int j = c[i] + 1; j < n; j++){
dp[i][j] = (dp[i-1][j - c[i] - 1] | dp[i][j-1]) & safe(j, c[i]);
}
}
for (int i = k - 1; i > 0; i--){
for (int j = 0; j < n; j++){
if (dp[i][j] && (j == n-1 || !dp[i][j + 1])) {
for (int l = j; l >= max(j - c[i], 0); l--) {
dp[i-1][l] = 0;
}
}
}
}
for (int i = 0; i < k; i++){
int parts = 0;
l[i] = r[i] = -1;
for (int j = 0; j < n; j++){
if (dp[i][j]) {
if (j == 0 || !dp[i][j-1]) parts++;
if (l[i] == -1) l[i] = j;
r[i] = j;
for (int l = j - c[i] + 1; l <= j; l++){
icl[l] = 1;
rs[l] = '?';
}
}
}
if (parts == 1) {
// cout << i << " " << l[i] << " " << r[i] << "\n";
// l[i] - c[i] + 1, r[i] reunion
// r[i] - c[i] + 1, l[i] intersection
for (int j = r[i] - c[i] + 1; j <= l[i]; j++) {
rs[j] = 'X';
}
}
}
for (int i = 0; i < n; i++){
if (rs[i] == '.') rs[i] = '_';
}
// for (int i = 0; i < k; i++){
// for (int j = 0; j < n; j++){
// cout << dp[i][j];
// }
// cout << "\n";
// }
return rs;
}
// string solve_puzzle(string s, vector<int> c) {
// int n = s.size();
// int k = c.size();
// string rs = s;
// auto find = [&] (int ps, int k, bool rev) {
// int sf = 0;
// if (rev) {
// for (int i = ps; i >= 0; i--){
// if (s[i] == '.') sf++;
// else sf = 0;
// if (sf == k) return i + sf - 1;
// }
// return -1;
// }
// for (int i = ps; i < n; i++){
// if (s[i] == '.') sf++;
// else sf = 0;
// if (sf == k) return i;
// }
// return -1;
// };
// for (int i = 0; i < k; i++) l[i] = 1e9, r[i] = -1;
// l[0] = find(0, c[0], 0);
// for (int i = 1; i < k; i++){
// l[i] = find(l[i-1] + 2, c[i], 0);
// }
// r[k-1] = find(n-1, c[k-1], 1);
// for (int i = k - 2; i >= 0; i--){
// r[i] = find(r[i + 1] - c[i + 1] - 1, c[i], 1);
// }
// for (int i = 0; i < k; i++){
// // l[i] - c[i] + 1, r[i] reunion
// // r[i] - c[i] + 1, l[i] intersection
// for (int j = r[i] - c[i] + 1; j <= l[i]; j++) {
// rs[j] = 'X';
// }
// }
// vector <int> ps;
// for (int i = 0; i < n; i++){
// if (s[i] == '_') ps.push_back(i);
// }
// for (int i = 0; i < ps.size() - 1; i++){
// }
// for (int i = 0; i < n; i++){
// if (i - 1 >= 0 && i + 1 < n && rs[i-1] == 'X' && rs[i + 1] == 'X' && rs[i] == '.') rs[i] = '_';
// else if (rs[i] == '.') rs[i] = '?';
// }
// return rs;
// }
