String Currency

Interview

Time limit1sMemory limit256 MB

Summary

Find the lexicographically smallest string of length N over A-Z, where letter values 1 to 26 sum to exactly X, or print ! if impossible.

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

Problem

Hana visited Primenara last year, and this year she plans to tour Stringnara. In Stringnara, strings made of uppercase English letters are used as currency.

In Stringnara, 'A' has value 1, 'B' has value 2, ..., 'Z' has value 26, and these letters are concatenated to form strings used as currency. For example, the value of "HONGIK" is 8 + 15 + 14 + 7 + 9 + 11 = 64.

After the stress of Primenara's unusual currency, Hana now wants to plan her spending exactly and exchange her money for string currency in advance. She will take exactly one string, its length must be $N$ , and its value must be $X$ . It must of course consist only of uppercase English letters.

The exchange office gives priority to strings that come earlier in lexicographic order! To help Hana, who is distracted by her travel preparations, find the lexicographically smallest string that satisfies the conditions.

Input

The first line contains the length of the string $N$ ( $1 \le N \le 5{,}000{,}000$ ) and the integer $X$ representing the value of the string ( $1 \le X \le 500{,}000{,}000$ ), separated by a space.

Output

On the first line, print the lexicographically smallest string among those that satisfy the conditions. If no such string exists, print "!" (without quotes).

Examples2

Example 1
Input
```
6 64
```
Expected output
```
AAAIZZ
```
Example 2
Input
```
6 157
```
Expected output
```
!
```