Ideal String

Time limit2sMemory limit128 MB

Summary

Build the lexicographically smallest length-N string where each character's total occurrence count equals the position of its first appearance, or output -1 if none exists.

Level: Medium7 of 10
Topics: Greedy, Dynamic programming, Combinatorics, String
Solved: No attempts yet

Problem

Count positions in a string starting from 1. A string is ideal if, for every character in the string, the total number of times that character appears is equal to the position where it first appears.

For example, BAOOOA is an ideal string. B first appears at position 1 and appears 1 time in total. A first appears at position 2 and appears 2 times in total. O first appears at position 3 and appears 3 times in total.

Given the length N, print the lexicographically smallest ideal string of length N. If no such string exists, print -1.

Input

The first line contains a natural number N. (1 <= N <= 100)

Output

Print the answer string on one line.

Examples6

Example 1
Input
```
3
```
Expected output
```
ABB
```
Example 2
Input
```
1
```
Expected output
```
A
```
Example 3
Input
```
2
```
Expected output
```
-1
```
Example 4
Input
```
6
```
Expected output
```
ABCBCC
```
Example 5
Input
```
7
```
Expected output
```
ABBCCCC
```
Example 6
Input
```
5
```
Expected output
```
-1
```