#include <bits/stdc++.h>
#include "paint.h"
using namespace std;
const int maxn = 102;
vector <vector <int> > v[maxn];
// string solve_puzzle(string s, vector<int> c) {
// int n = s.size();
// int k = c.size();
// string rs = s;
// for (int i = 0; i + c[0] - 1 < n; i++){
// bool good = 1;
// for (int j = i; j < i + c[0] - 1; j++){
// if (s[j] == '_') good = 0;
// }
// if (good) v[0].push_back(vector <int> (1, i + c[0] - 1));
// }
// for (int i = 1; i < k; i++){
// for (auto &vc: v[i-1]){
// int idx = vc.back();
// for (int j = idx + 2; j + c[i] - 1 < n; j++) {
// bool good = 1;
// for (int k = j; k < j + c[i] - 1; k++) {
// if (s[k] == '_') {
// good = 0;
// break;
// }
// }
// if (good) {
// vector <int> s = vc;
// s.push_back(j + 2 + c[i] - 1);
// v[i].push_back(s);
// }
// }
// }
// }
// for (auto &i: v[1]) {
// for (int &j: i) {
// cout << j << " ";
// }
// cout << "\n";
// }
// return "";
// }
// int dp[maxn][maxn][2]; // dp[i][j][k] -> (k == 0 ? min: max) position for the last X on the j-th partition considering first i partitions
int dp[maxn][maxn]; // dp[i][j] -> if you can finish i-th partition on the position j
int l[maxn];
int r[maxn];
string solve_puzzle(string s, vector<int> c) {
int n = s.size();
int k = c.size();
string rs = s;
for (int i = 0; i < k; i++) l[i] = 1e9, r[i] = -1;
l[0] = c[0] - 1;
for (int i = 1; i < k; i++){
l[i] = l[i-1] + c[i] + 1;
}
r[k-1] = n-1;
for (int i = k - 2; i >= 0; i--){
r[i] = r[i + 1] - c[i + 1] - 1;
}
// for (int i = 0; i < k; i++){
// cout << i << " " << l[i] << " " << r[i] << "\n";
// }
for (int i = 0; i < k; i++){
// cout << l[i] << " " << l[i] + c[i] - 1 << " " << r[i] - c[i] + 1 << " " << r[i] << "\n";
for (int j = r[i] - c[i] + 1; j <= l[i]; j++) {
rs[j] = 'X';
}
}
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;
}
