Hide

Problem I
Inspiration Manifestation

Rarity is designing new clothes, and she is looking for some inspiration! Recently, she learned about the importance of symmetry, and is trying to find ways to incorporate this idea into her designs.

To learn more about symmetry, she decided to search for inspiration in a naturally-symmetric concept, palindromes. A palindrome is a string that reads the same forwards and backwards. For example, peep and deified are palindromes, while tepee and defied are not.

A substring of a string is a string that can be formed by removing zero or more characters from the start and end of the other string. For example, sig and design are substrings of design, while dig and signed are not.

Rarity wants to find the perfect amount of symmetry to incorporate into her new design; to this end, she wants to find a string consisting only of lowercase Latin alphabet characters that

  1. has length exactly $N$,

  2. has exactly $K$ distinct characters, and

  3. whose longest palindromic substring has length exactly $P$.

Help her find any string that satisfies all her requirements, or tell her that what she wants is impossible.

Input

The first and only line of input contains exactly three integers, $N$ ($1 \leq N \leq 10^6$), $K$ ($1 \leq K \leq 26$) and $P$ ($1 \leq P \leq N$), the requirements of the string.

Output

Output on a line by itself:

  • a string satisfying all her requirements, if any such string exists, or

  • IMPOSSIBLE, otherwise.

If there are multiple correct answers, you can output any of them.

Sample Input 1 Sample Output 1
6 5 3
rarity
Sample Input 2 Sample Output 2
9 8 1
canterlot
Sample Input 3 Sample Output 3
5 3 5
madam
Sample Input 4 Sample Output 4
2 2 2
IMPOSSIBLE

Please log in to submit a solution to this problem

Log in