Problem H
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 |
