Problem D
Counting Satellites
Nick likes satellites. He likes them so much that he looks for them everywhere. One day he found a string of letters and counted a lot of instances of the word “SATELLITE” among all subsequences of the string. However the next day he forgot this string. Can you help him construct such a string?
String $s$ is a subsequence of string $t$ if and only if it is possible to delete some (possibly zero) characters from $t$ to get $s$. Two subsequences are considered different if some character at a given position in $t$ is deleted in one subsequence but not the other.
Input
The single line of input contains a single integer $k$ ($1 \leq k \leq 10^{18})$, which is the number of instances of the word “SATELLITE” in the string Nick forgot.
Output
Output a string of at most $5\, 000$ uppercase letters. The string must have exactly $k$ instances of the word “SATELLITE” among all its subsequences. It can be proven that under the given constraints a solution always exists. Note that the length of the string does not have to be minimized.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 |
SATELLITE |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 |
NICKLIKESSATELLITES |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 |
SSSATELLITE |
| Sample Input 4 | Sample Output 4 |
|---|---|
19 |
SATELLITESATELLITE |
