题目描述

厌倦了解几何题，你决定解决下面的构造问题：找到一个长度为 $n$ 的字符串，使其恰好包含 $k$ 个（不一定连续的）子序列 NAC。

然而，这个问题似乎太熟悉了。转折点在于——你的朋友已经给出了字符串的一部分，因此你必须填入剩余的字符！

输入格式

输入的第一行包含两个整数 $n$（$1 \le n \le 40$）和 $k$（$0 \le k \le 2{,}500$），其中 $n$ 是字符串的长度，$k$ 是输出字符串必须包含的（不一定连续的）子序列 NAC 的数量。

第二行包含一个长度为 $n$ 的字符串，仅由大写字母和/或问号组成。

输出格式

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

22 2
N??A??????C???????????

NOTANOTHERCONSTRUCTIVE

18 0
COUNTINGSATELLITES

COUNTINGSATELLITES

2 1
??

-1

提示

翻译由 DeepSeek V3.2 完成