CPM Banner

Program time limit: 1 second

Program memory limit: 512 MB

You are designing a banner for CPM (Competitive Programming Masters) and want to make it as short as possible while still being recognizable. The banner should contain the letters "CPM" as a subsequence exactly $N$ times.

You are given an initial string that must be a prefix of your final banner. Given $N$ and the initial string, output the shortest string where "CPM" appears as a subsequence exactly $N$ times and starts with the given initial string. If there are multiple strings of equal length, output the lexicographically smallest one. If it's impossible to satisfy the constraints, output "impossible".

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. For example, "CPM" appears as a subsequence in "CCPMM" four times (after removing elements at positions $(1, 4), (1, 5), (2, 4) or (2, 5)$).

Input

The first line of input contains an integer $N$, representing the number of times "CPM" should appear as a subsequence.
The second line contains an integer $L$, representing the length of the initial string.
The third line contains a string $S$ of length $L$ (consisting only of characters 'C', 'P', 'M'), representing the initial string that must be a prefix of the answer.

Constraints

For all test cases:

$1 \le N \le 200$
$1 \le L \le 500$ where $L$ is the length of string $S$
String $S$ contains only characters 'C', 'P', 'M'

Output

Output a single string, which is the shortest string containing "CPM" as a subsequence exactly N times and starting with the given initial string. If there are multiple strings of equal length, output the lexicographically smallest one. If it's impossible to satisfy the constraints, output "impossible".

Templates

You should read from standard input and write to standard output.

In Python, you could use the following code.

# Taking inputs, already done! :D
N = int(input())
L = int(input())
S = input().strip()

result = ""
# Write your code here


# Printing output
print(result)

In C or C++, you could use the following code.

// Taking inputs, already done! :D
int N; scanf("%d", &N);
int L; scanf("%d", &L);
char S[505]; scanf("%s", S);

string result;
// Write your code here


// Printing output
printf("%s\n", result.c_str());

Sample Input 1

1
3
CPM

Sample Output 1

CPM

Explanation 1

We have an initial string "CPM" and need exactly 1 occurrence of "CPM" as a subsequence. The shortest string is "CPM" itself, which has length 3 and starts with the given initial string.

Sample Input 2

2
2
CC

Sample Output 2

CCPM

Explanation 2

We have an initial string "CC" and need exactly 2 occurrences of "CPM" as a subsequence. The shortest string satisfying this is "CCPM", where "CPM" appears at positions (1, 3, 4) and (2, 3, 4).

Sample Input 3

1
3
CPP

Sample Output 3

impossible

Explanation 3

We have an initial string "CPP" and need exactly one occurance of "CPM". This is impossible as we must add an "M" at some point, but adding one would create at least two "CPM"s.

Scoring

Your program will be run on both sample cases and 20 secret cases one after another, and if it produces the correct output for all test cases, it solves this task. Recall that your final score on the task is the score of your highest scoring submission.