또 다른 구성 문제는 아니다!

기하 문제에 지친 당신은 대신 다음 구성 문제를 풀기로 한다. 길이가 $n$인 문자열 중 NAC의 부분 수열이 정확히 $k$개 들어 있는 문자열을 찾아라. 부분 수열은 연속일 필요가 없다. 친구가 문자열의 일부를 미리 주었으므로, 나머지 자리를 채워야 한다.

첫 번째 줄에 두 정수 $n$ ($1 \le n \le 40$)과 $k$ ($0 \le k \le 2\,500$)이 주어진다. $n$은 문자열의 길이, $k$는 출력 문자열에 포함되어야 하는 NAC 부분 수열의 개수다.

두 번째 줄에는 길이가 정확히 $n$인 문자열이 주어진다. 문자열은 대문자와 물음표(?)로만 이루어진다.

물음표를 대문자로 바꾼 문자열을 한 줄에 출력한다. 결과 문자열에 NAC 부분 수열이 정확히 $k$개 있어야 한다. 입력에 있는 대문자는 원래 위치를 그대로 유지해야 한다. 그런 문자열이 없으면 -1을 출력한다. 답이 여러 개일 수 있으며, 올바른 답이면 어떤 것이든 인정된다.