Hide

Problem I
Not Another Constructive!

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!

Input

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

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.

Sample Input 1 Sample Output 1
22 2
N??A??????C???????????
NOTANOTHERCONSTRUCTIVE
Sample Input 2 Sample Output 2
18 0
COUNTINGSATELLITES
COUNTINGSATELLITES
Sample Input 3 Sample Output 3
2 1
??
-1

Please log in to submit a solution to this problem

Log in