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 ≤ n ≤ 40)$ and $k (0 ≤ k ≤ 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.