#include "paint.h"
#include <bits/stdc++.h>
#include <cstdlib>
using namespace std;
int n, k;
const int mxn = 5005, mxk = 105;
bool ok(int l, int r, vector<char> &s_u) {
for (int i = l; i <= r; i++) if (s_u[i] == '_') return false;
if (s_u[r + 1] == 'X' || s_u[l - 1] == 'X') return false;
return true;
}
void do_dp(vector<vector<vector<int>>> &dp, vector<char> &s_u, vector<int> &c_u) {
dp[0][0][0] = 1; dp[0][0][1] = 1;
for (int i = 1; i <= n; i++) {
if (s_u[i] != 'X') {
dp[i][0][0] = dp[i - 1][0][0];
dp[i][0][1] = dp[i - 1][0][1];
}
for (int j = 1; j <= k; j++) {
if (s_u[i] != 'X') {
dp[i][j][0] = (dp[i - 1][j][0] || dp[i - 1][j][1]);
}
if (s_u[i] != '_') {
if (i >= c_u[j]) {
// cout << "setting " << i - c[j] << " " << j - 1 << "\n";
if (ok(i - c_u[j] + 1, i, s_u)) dp[i][j][1] = dp[i - c_u[j]][j - 1][0];
}
}
}
}
}
string solve_puzzle(string si, vector<int> ci) {
n = (int)si.size(); k = (int)ci.size();
vector<char> s_norm(n+5, '!'), s_rev(n+5, '!');
vector<int> c_norm, c_rev;
for (int i = 1; i <= n; i++) s_norm[i] = si[i - 1];
for (int i = n; i >= 1; i--) s_rev[i] = si[n - i];
c_norm.push_back(-1e9);
for (auto &x : ci) c_norm.push_back(x);
c_rev.push_back(-1e9);
for (int i = k - 1; i >= 0; i--) c_rev.push_back(ci[i]);
vector<vector<vector<int>>> dp(mxn, vector<vector<int>>(mxk, vector<int>(2))), dp2(mxn, vector<vector<int>>(mxk, vector<int>(2)));
do_dp(dp, s_norm, c_norm);
do_dp(dp2, s_rev, c_rev);
// reverse(dp2.begin(), dp2.end());
// for (auto &x : s_norm) cout << x;
// cout << '\n';
// for (auto &x : s_rev) cout << x;
// cout << '\n';
// cout << "pref:\n";
// for (int i = 1; i <= n; i++) {
// for (int j = 0; j <= k; j++) {
// for (int k = 0; k <= 1; k++) {
// cout << i << " " << j << " " << k << ": " << dp[i][j][k] << '\n';
// }
// }
// }
// cout << "suf:\n";
// for (int i = 1; i <= n; i++) {
// for (int j = 0; j <= k; j++) {
// for (int k = 0; k <= 1; k++) {
// cout << i << " " << j << " " << k << ": " << dp2[n - i + 1][j][k] << '\n';
// }
// }
// }
vector<vector<int>> maxpref(n+3, vector<int>(2)), maxsuf(n + 3, vector<int>(2));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
if (dp[i][j][0]) maxpref[i][0] = j;
if (dp[i][j][1]) maxpref[i][1] = j;
if (dp2[n - i + 1][j][0]) maxsuf[i][0] = j;
if (dp2[n - i + 1][j][1]) maxsuf[i][1] = j;
}
}
// cout << "maxpref:\n";
// for (int i = 0; i <= n; i++) {
// cout << maxpref[i][0] << " " << maxpref[i][1] << '\n';
// }
// cout << "maxsuf:\n";
// for (int i = 0; i <= n; i++) {
// cout << maxsuf[i][0] << " " << maxsuf[i][1] << '\n';
// }
string ans(n, '!');
for (int i = 1; i <= n; i++) {
if (si[i - 1] != '.') {
ans[i - 1] = si[i - 1];
continue;
}
bool w = false, bk = false;
for (int bl = 0; bl <= k; bl++) {
int br = k - bl;
if (dp[i][bl][0] && dp2[n - i + 1][br][0]) w = true;
}
for (int b = 1; b <= k; b++) {
// bth block covers this
// cout << "its " << c_norm[b] - 1 << '\n';
// cout << n << " " << k << '\n';
if (c_norm[b] > n) return ans;
for (int j = i; j <= i + c_norm[b] - 1; j++) {
if (j > n) break;
if (!dp[j][b][1]) continue;
int sf = maxsuf[j + 1][0];
if (sf + b >= k) bk = true;
}
}
// cout << i << " " << w << " " << bk << '\n';
// assert(w || bk);
if (w && !bk) ans[i - 1] = '_';
else if (!w && bk) ans[i - 1] = 'X';
else if (w && bk) ans[i - 1] = '?';
else ans[i - 1] = 'L';
}
return ans;
}
