FizzBuzz

Time limit1sMemory limit512 MB

Summary

Given an index s up to 10^18, output the 20 characters of the FizzBuzz String starting at position s.

Level: Medium4 of 10
Topics: Math, Implementation, String, Binary search
Solved: No attempts yet

Problem

FizzBuzz is a game in which the integers 1 and up are said in order according to the following rules.

"Fizz" when divisible by 3
"Buzz" when divisible by 5
"FizzBuzz" when divisible by both 3 and 5
Otherwise, the number itself

An example of how the game proceeds is shown below.

1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16, …

The result of joining the spoken words into a single string is called the FizzBuzz String. Given an index s, output 20 characters starting from the s-th character of the FizzBuzz String. The index starts at 1, and the string is long enough (at least s+20).

Input

The input is given in the following format.

Output

Output 20 characters starting from the s-th character of the FizzBuzz String on one line.

Constraints

s is an integer.
1 ≤ s ≤ 1018

Examples3

Example 1
Input
```
1
```
Expected output
```
12Fizz4BuzzFizz78Fiz
```
Example 2
Input
```
20
```
Expected output
```
zzBuzz11Fizz1314Fizz
```
Example 3
Input
```
10000000000
```
Expected output
```
93FizzBuzz1418650796
```