Palindrome Name

Interview

Time limit1sMemory limit1024 MB

Summary

Build a string of length N using exactly K distinct lowercase letters that has the most distinct palindromic substrings, choosing the lexicographically smallest on ties.

Level: Medium4 of 10
Topics: Greedy, Math, Implementation
Solved: No attempts yet

Problem

Edge, a wizard of palindromes, was looking for palindromes again today. Along the way, he wanted to hold a festival for people who love palindromes. The festival name must have length $N$ and must consist of exactly $K$ distinct lowercase English letters. Among the names that satisfy these conditions, Edge picks the one with the largest number of distinct palindromic substrings as the festival name. For the meanings of the terms used in the problem, see the hints below.

Input

The first line contains the name length $N$ and the number of lowercase letters $K$ , separated by a space. $(1 \le N \le 100\,000, 1 \le K \le 26, K \le N)$

Output

On the first line, print the festival name that Edge will choose.

Hint

A palindrome reads the same forward and backward. For example, level is a palindrome, but apple is not.

A substring is a string made by joining some consecutive characters of a string. For example, the substrings of aba are a, b, a, ab, ba, and aba.

Two substrings A and B are different if their lengths differ, or if there is some index i where the i-th character of A differs from the i-th character of B. Distinct substrings are the substrings that differ from each other. For example, the distinct substrings of aba are a, b, ab, ba, and aba.

Lexicographic order is the order in which strings appear in a dictionary. For example, abc comes before acb, and aa comes before aaa.

Examples3

Example 1
Input
```
1 1
```
Expected output
```
a
```
Example 2
Input
```
2 1
```
Expected output
```
aa
```
Example 3
Input
```
2 2
```
Expected output
```
ab
```