P16090 [ICPC 2024 NAC] Not Another Constructive!

厌倦了解几何题，你决定解决下面的构造问题：找到一个长度为 $ n $ 的字符串，使其恰好包含 $ k $ 个（不一定连续的）子序列 `NAC`。 然而，这个问题似乎太熟悉了。转折点在于——你的朋友已经给出了字符串的一部分，因此你必须填入剩余的字符！

输入的第一行包含两个整数 $ n $（$ 1 \le n \le 40 $）和 $ k $（$ 0 \le k \le 2{,}500 $），其中 $ n $ 是字符串的长度，$ k $ 是输出字符串必须包含的（不一定连续的）子序列 `NAC` 的数量。 第二行包含一个长度为 $ n $ 的字符串，仅由大写字母和/或问号组成。

输出一个大写字母字符串，将输入字符串中的每个问号替换成一个大写字母，使得得到的字符串恰好包含 $ k $ 个子序列 `NAC`。如果不可能做到，则输出 $ -1 $。输入字符串中的任何大写字母必须保留在它们的位置上。对于任何给定的测试用例，可能存在多个解；任何正确的解都将被接受。

翻译由 DeepSeek V3.2 完成