Letters

Time limit0.2sMemory limit256 MB

Summary

Given index i, return the uppercase letter at position i in the concatenation of all uppercase strings ordered by length then lexicographically.

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

Problem

Write down every string of uppercase letters in this order. First the strings of length 1: A, B, …, Z. Then the strings of length 2: AA, AB, …, AZ, BA, BB, …, ZZ. Then the strings of length 3, and so on, with the length growing by one forever. Strings of the same length are listed in lexicographic order.

Concatenating that list from the start gives one endless sequence of uppercase letters. Number the letters of the sequence starting at 0 for the first one. Given an index, find the letter at that position.

Input

The first line contains the index $i$ of a letter. ( $0 \le i \le 2 \times 10^9$ )

Output

Print the single uppercase letter at position $i$ of the sequence.

Examples7

Example 1
Input
```
0
```
Expected output
```
A
```
Example 2
Input
```
25
```
Expected output
```
Z
```
Example 3
Input
```
50
```
Expected output
```
A
```
Example 4
Input
```
100
```
Expected output
```
B
```
Example 5
Input
```
250
```
Expected output
```
E
```
Example 6
Input
```
500
```
Expected output
```
J
```
Example 7
Input
```
1000
```
Expected output
```
S
```