注意事项

在 LibreOJ 上，由于语言限制，目前只支持以下语言的提交：

• C++（标准为 C++ 11 及以上）

请在提交源代码前添加 #include "paint.h"。

题目描述

按数目填色是个有名的智力游戏。我们现在考虑的是这个游戏的一维版本。在这个游戏中，玩家会有一行 $n$ 个方格。这些方格从左到右分别编号为 $0$ 至 $n - 1$ 。玩家必须要为这些方格填上黑色或白色。我们用 X 代表填上黑色的方格并用 _ 来代表填上白色的方格。

系统将会给玩家一个提示，这个提示是一个含有 $k$ 个正整数的序列 $c = [c_0, \ldots, c_{k-1}]$ 。而玩家必须要根据提示为方格填色，填色的要求是在这行上，填上黑色的方格必须组成 $k$ 个连续的区间。而且，在由左开始的第 $i$（由 $0$ 开始）个区间上必须含有 $c_i$ 个黑色方格。例如，若提示为 $c = [3, 4]$，则该游戏的正确填色方法是必须含有两个由连续黑色格位组成的区间, 这两个区间的长度分别是 $3$ 和 $4$。因此，若 $n = 10$ 且 $c = [3, 4]$ 的话，则满足提示的一个正确填色方法是 _XXX__XXXX。要注意的是 XXXX_XXX__ 并不满足提示, 因为黑色区间的长度顺序不正确。同时 __XXXXXXX_ 也不满足提示，因为它只含有一个黑色区间而非两个分开的黑色区间。

你将获得一个部分方格已填好颜色的游戏行格。即，你知道 $n$ 及 $c$ 的值，并且你也知道有些方格一定是黑色和有些方格一定是白色。你的工作是从中推算出更详细的方格的信息。

更加详细来说，一个正确的游戏解应该满足提示，并且和已经知道颜色的方格的颜色一致。你的程序必须找出在所有正确的游戏解中都会填上黑色的方格和在所有正确的游戏解中都会填上白色的方格。

你可以假设每个输入一定存在至少一个正确的游戏解。

实现细节

你必须编写程序以实现以下的函数（或方法）：

• string solve_puzzle(string s, int[] c)
  • s：一个含有 $n$ 个字符的字符串。而对于每个 $i$（$0 \leq i \leq n - 1$），字符 $i$ 将会是以下其中一个:
    • X，表示方格 $i$ 必须要填上黑色，
    • _，表示方格 $i$ 必须要填上白色，
    • .，表示方格 $i$ 没有任何信息。
  • c：是一个长度为 $k$ 的数组，它的内容是上面叙述中所讲的提示，
  • 这函数必须要返回一个长度为 $n$ 的数组。对于每个 $i$（$0 \leq i \leq n - 1$）而言，输出字符串的第 $i$ 个字符应该是以下其中一个:
    • X，表示在所有游戏解中，第 $i$ 个方格都是填上黑色，
    • _，表示在所有游戏解中，第 $i$ 个方格都是填上白色，
    • ?，表示其他情况 (即该游戏中存在两个正确的游戏解，且其中一个解该方格是填上黑色，但在另一解中该方格是填上白色)。

在 C 语言中，函数的参数略有不同：

• void solve_puzzle(int n, char* s, int k, int* c, char* result)
  • n：字符串 s 的长度（即方格的数目)，
  • k：数组 c 的长度（即提示序列的长度)，
  • 其他的参数同上，
  • 该函数应把答案写到字符串 result 内，而不是返回一个长度为 $n$ 的字符串。

在本题目中使用到的字符的 ASCII 代码如下：

• X：88，
• _：95，
• .：46，
• ?：63。

请使用提供的模板文件，以获得关于你所使用的编程语言的实现细节。

样例 1

solve_puzzle("..........", [3, 4])

以下是这次游戏的所有正确的解：

• XXX_XXXX__，
• XXX__XXXX_，
• XXX___XXXX，
• _XXX_XXXX_，
• _XXX__XXXX，
• __XXX_XXXX.

你可以观察到下标为 $2$，$6$，和 $7$（从 $0$ 开始）的方格在所有正确的解中都是黑色。而其他的所有方格可能但不一定是黑色的。所以正确的答案应该是 "??X???XX??"。

样例 2

solve_puzzle("........", [3, 4])

在这个样例中，正确的填色方法只有一种，即 XXX_XXXX。

样例 3

solve_puzzle("..._._....", [3])

在这个样例中，我们可以推出方格 $4$ 一定是白色，因为在白色的方格 $3$ 和 方格 $5$ 之间根本不可能容纳 $3$ 个连续的黑色方格。因此正确的答案应该是 ???___????。

样例 4

solve_puzzle(".X........", [3])

只有两个正确解符合上述描述：

• XXX_______，
• _XXX______。

因此，正确的答案是 ?XX?______。

子任务

在所有的子任务中 $1 \leq k \leq n$，$1 \leq c_i \leq n$（对于每个 $0 \leq i \leq k - 1$） 。

1. （7 分）$n \leq 20$，$k = 1$，$s$ 只含有字符 .（即是空白的游戏行格），
2. （3 分）$n \leq 20$，$s$ 只含有字符 .，
3. （22 分）$n \leq 100$，$s$ 只含有字符 .，
4. （27 分）$n \leq 100$，$s$ 只含有字符 . 及 _（只有关于填上了白色的方格信息），
5. （21 分）$n \leq 100$，
6. （10 分）$n \leq 5\,000$，$k \leq 100$，
7. （10 分）$n \leq 200\,000$，$k \leq 100$。

样例评测程序

样例评测程序将会按照下列格式读取输入数据：

• 第一行：字符串 $s$，
• 第二行：整数 $k$ 随后有 $k$ 个整数 $c_0, \ldots, c_{k-1}$。