31957번 - 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!

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.