题目描述

Sick of solving geometry problems, you decide to solve the following constructive problem: find a string of length $n$ that contains exactly $k$ not necessarily contiguous subsequences of NAC.

This problem seems too familiar though. Here’s the twist - your friend has given you part of the string, so you must fill in the remaining characters!

输入格式

The first line of input contains two integers $n$ ($1 \le n \le 40$) and $k$ ($0 \le k \le 2,500$), where $n$ is the length of the string and $k$ is the number of not necessarily contiguous subsequences of NAC that the output must contain.

The second line contains a string of length exactly $n$, consisting only of uppercase letters and/or question marks.

输出格式

Output a string of upper case letters, replacing each question mark in the input string with an uppercase letter so that the resulting string has exactly $k$ subsequences of NAC. If this is not possible, output $-1$. Any uppercase letters in the input string must be kept in their position. There may be multiple possible solutions for any given test case; any correct solution will be accepted.

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

NOTANOTHERCONSTRUCTIVE

18 0
COUNTINGSATELLITES

COUNTINGSATELLITES

2 1
??

-1