import java.util.*; /** * Perform a search, keeping track of the number of N's, the number of NA's, and the number of NAC's. * Exit early if it is not possible to reach the target with the remaining characters or if we * have exceeded the target. * * @author Finn Lidbetter */ public class notanotherconstructive_finn { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); sc.nextLine(); char[] chars = sc.nextLine().toCharArray(); Integer[][][] upperBound = new Integer[n][n][n*n]; upperBound(upperBound, 0, 0, 0); HashMap path = new HashMap<>(); State curr = new State(-1, 0, 0, 0); State finalState = solve(curr, path, chars, k, upperBound); if (finalState == null) { System.out.println(-1); return; } StringBuilder ans = new StringBuilder(); curr = finalState; System.out.println(getPath(finalState, path)); } static String getPath(State curr, HashMap path) { StringBuilder ans = new StringBuilder(); while (curr.index != -1) { char ch = path.get(curr); ans.append(ch); State prev; if (ch == 'C') { prev = new State(curr.index - 1, curr.nCount, curr.naCount, curr.nacCount - curr.naCount); } else if (ch == 'A') { prev = new State(curr.index - 1, curr.nCount, curr.naCount - curr.nCount, curr.nacCount); } else if (ch == 'N') { prev = new State(curr.index - 1, curr.nCount - 1, curr.naCount, curr.nacCount); } else { prev = new State(curr.index - 1, curr.nCount, curr.naCount, curr.nacCount); } curr = prev; } ans.reverse(); return ans.toString(); } static int upperBound(Integer[][][] dp, int i, int j, int k) { if (i>=dp.length) { return 0; } if (dp[i][j][k]!=null) { return dp[i][j][k]; } // This will never be best, but use it to populate dp. int appendB = upperBound(dp, i+1, j, k); int appendN = upperBound(dp, i+1, j+1, k); int appendA = upperBound(dp, i+1, j, k+j); int appendC = upperBound(dp, i+1, j, k) + k; int best = appendN; if (appendA>best) { best = appendA; } if (appendC>best) { best = appendC; } dp[i][j][k] = best; return best; } static State solve(State curr, HashMap path, char[] chars, int target, Integer[][][] upperBound) { int nextIndex = curr.index + 1; if (nextIndex>=chars.length) { if (curr.nacCount==target) { return curr; } else { return null; } } if (curr.nacCount>target) { return null; } int remaining = chars.length-curr.index; Integer maxReachable = upperBound[nextIndex][curr.nCount][curr.naCount]; if (maxReachable!=null && maxReachable + curr.nacCount