Counting Satellites

시간 제한1초메모리 제한1024 MB

요약

k(최대 10^18)가 주어질 때, 부분수열로 SATELLITE를 정확히 k번 포함하는 5000자 이하의 대문자 문자열을 만든다.

난이도: 보통10점 중 6점
유형: 조합론, 동적 계획법, 그리디, 구현
정답자: 아직 제출이 없습니다

문제

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.

입력

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 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.

예제4

예제 1
입력
```
1
```
예상 출력
```
SATELLITE
```
예제 2
입력
```
2
```
예상 출력
```
NICKLIKESSATELLITES
```
예제 3
입력
```
3
```
예상 출력
```
SSSATELLITE
```
예제 4
입력
```
19
```
예상 출력
```
SATELLITESATELLITE
```