Non-Repeating Word

Time limit2sMemory limit128 MB

Summary
Find the lexicographically smallest length-N string over the first A letters that never contains K consecutive copies of any nonempty block.
Level

Hard8 of 10

Topics
Backtracking, String, Greedy, Brute force
Solved
No attempts yet

Problem

A positive integer K is given. A string S is called K-repeat-free if there is no nonempty string T such that T repeated K consecutive times appears as a substring of S.

Given K, N, and A, find the lexicographically smallest word of length N that is K-repeat-free and uses only the first A uppercase English letters.

Input

The first line contains three integers K, N, and A.

Output

Print the required word. If no such word exists, print -1.

Constraints

  • 2 <= K <= 10
  • 1 <= N <= 50
  • 1 <= A <= 26

Examples4

  1. Example 1

    Input
    3 5 2
    Expected output
    AABAA

  2. Example 2

    Input
    3 5 1
    Expected output
    -1

  3. Example 3

    Input
    3 10 2
    Expected output
    AABAABABAA

  4. Example 4

    Input
    3 50 2
    Expected output
    AABAABABAABAABBAABAABABAABAABBAABAABABAABABBAABAAB