A8897. Polo the Penguin and Strings
编程题
普及/提高-
知识点
题目描述
Little penguin Polo adores strings. But most of all he adores strings of length $n$ .
One day he wanted to find a string that meets the following conditions:
1. The string consists of $n$ lowercase English letters (that is, the string's length equals $n$ ), exactly $k$ of these letters are distinct.
2. No two neighbouring letters of a string coincide; that is, if we represent a string as $s=s_{1}s_{2}...\ s_{n}$ , then the following inequality holds, $s_{i}≠s_{i+1}(1<=i<n)$ .
3. Among all strings that meet points 1 and 2, the required string is lexicographically smallest.
Help him find such string or state that such string doesn't exist.
String $x=x_{1}x_{2}...\ x_{p}$ is lexicographically less than string $y=y_{1}y_{2}...\ y_{q}$ , if either $p<q$ and $x_{1}=y_{1},x_{2}=y_{2},...\ ,x_{p}=y_{p}$ , or there is such number $r$ $(r<p,r<q)$ , that $x_{1}=y_{1},x_{2}=y_{2},...\ ,x_{r}=y_{r}$ and $x_{r+1}<y_{r+1}$ . The characters of the strings are compared by their ASCII codes.
One day he wanted to find a string that meets the following conditions:
1. The string consists of $n$ lowercase English letters (that is, the string's length equals $n$ ), exactly $k$ of these letters are distinct.
2. No two neighbouring letters of a string coincide; that is, if we represent a string as $s=s_{1}s_{2}...\ s_{n}$ , then the following inequality holds, $s_{i}≠s_{i+1}(1<=i<n)$ .
3. Among all strings that meet points 1 and 2, the required string is lexicographically smallest.
Help him find such string or state that such string doesn't exist.
String $x=x_{1}x_{2}...\ x_{p}$ is lexicographically less than string $y=y_{1}y_{2}...\ y_{q}$ , if either $p<q$ and $x_{1}=y_{1},x_{2}=y_{2},...\ ,x_{p}=y_{p}$ , or there is such number $r$ $(r<p,r<q)$ , that $x_{1}=y_{1},x_{2}=y_{2},...\ ,x_{r}=y_{r}$ and $x_{r+1}<y_{r+1}$ . The characters of the strings are compared by their ASCII codes.
输入格式
A single line contains two positive integers $n$ and $k$ $(1<=n<=10^{6},1<=k<=26)$ — the string's length and the number of distinct letters.
输出格式
In a single line print the required string. If there isn't such string, print "-1" (without the quotes).
输入输出样例
输入 #1
7 4
输出 #1
ababacd
输入 #2
4 7
输出 #2
-1