Not Another Constructive!

Time limit1sMemory limit2048 MB

Summary

Given a partially filled string of length n up to 40, replace each question mark with an uppercase letter so the string has exactly k subsequences equal to NAC, or report -1.

Level: Medium6 of 10
Topics: Dynamic programming, String, Brute force
Solved: No attempts yet

Problem

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. Your friend has given you part of the string, so you must fill in the remaining characters.

Input

The first line 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 subsequences of NAC that the output must contain. Subsequences do not need to be contiguous.

The second line contains a string of length exactly $n$ , consisting only of uppercase letters and question marks.

Output

Output a string of uppercase letters, replacing each question mark in the input string with an uppercase letter so that the resulting string has exactly $k$ subsequences of NAC. Any uppercase letters in the input must keep their positions. If no such string exists, output -1. Multiple solutions may exist, and any correct solution is accepted.

Examples3

Example 1

Input

22 2
N??A??????C???????????

Expected output

NOTANOTHERCONSTRUCTIVE

Example 2

Input

18 0
COUNTINGSATELLITES

Expected output

COUNTINGSATELLITES

Example 3
Input
```
2 1
??
```
Expected output
```
-1
```