#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];
// string solve_puzzle_0(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++){
// 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;
// }
// void clear () {
// for (int i = 0; i < maxn; i++){
// l[i] = 1e9;
// r[i] = -1;
// for (int j = 0; j < maxn; j++){
// dp[i][j] = 0;
// }
// }
// }
string solve_puzzle(string s, vector<int> c) {
s.insert(s.begin(), '_');
s.insert(s.end(), '_');
int n = s.size();
int k = c.size();
vector <int> inc(n + 1);
vector <int> wk (n + 1, 0);
vector <int> blea (n + 1);
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
int lpos = -1;
int sf = 0;
for (int j = l[i] - c[i] + 1; j <= r[i]; j++){
inc[j]++;
if (rs[j] == '_') {
sf = 0;
if (lpos != -1) {
cout << lpos << " " << j << "\n";
for (int k = lpos; k <= j; k++){
if (j - lpos - 1 >= c[i]) wk[k] = 1;
}
}
lpos = j;
}
else {
sf++;
if (sf >= c[i]) {
for (int l = j; l >= j - sf + 1; l--) wk[l] = 1;
}
}
}
for (int j = r[i] - c[i] + 1; j <= l[i]; j++) {
if (rs[j] != '_') rs[j] = 'X';
}
}
for (int i = 0; i < n; i++){
if (!inc[i]) rs[i] = '_';
else if (rs[i] == '.' && !wk[i]) rs[i] = '_';
else 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.substr(1, n - 2);
}
