题目描述

你需要完成一个构造问题：给定长度为 $n$ 的部分字符串，其中一些位置已经给定为大写字母，另一些位置为问号 ?。你需要把每个问号替换成一个大写字母，使最终字符串中恰好有 $k$ 个不一定连续的子序列 NAC。

已给定的大写字母不能被修改。

如果有多种合法答案，输出任意一种即可；如果不存在合法答案，输出 -1。

输入格式

第一行包含两个整数 $n,k$。

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

约束：

• $1 \le n \le 40$；
• $0 \le k \le 2500$。

输出格式

如果存在合法替换方案，输出替换后的字符串。
如果不存在，输出 -1。

样例输入 #1

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

样例输出 #1

NOTANOTHERCONSTRUCTIVE

样例输入 #2

18 0
COUNTINGSATELLITES

样例输出 #2

COUNTINGSATELLITES

样例输入 #3

2 1
??

样例输出 #3

-1