P16090 [ICPC 2024 NAC] 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.