#include <algorithm>
#include <iostream>
#include <stdexcept>
#include <vector>

enum class Category
{
    Nothing,
    DivisibleBy3,
    DivisibleBy5,
    DivisibleBy3And5
};

/// Checks if the given number satisfies the given category.
bool IsAssignationCorrect(Category category, int x)
{
    switch (category)
    {
        case Category::Nothing:
            return x % 3 != 0 && x % 5 != 0;
        case Category::DivisibleBy3:
            return x % 3 == 0 && x % 5 != 0;
        case Category::DivisibleBy5:
            return x % 3 != 0 && x % 5 == 0;
        case Category::DivisibleBy3And5:
            return x % 3 == 0 && x % 5 == 0;
    }

    throw std::runtime_error("IsAssignationCorrect: Something really bad happens here!");
}

/// Computes the factorial of the given number. This function is normal, no need to be stupid without a reason.
uint64_t ComputeFactorial(uint64_t n)
{
    uint64_t result = 1;
    for (uint64_t i = 1; i <= n; ++i)
        result *= i;
    return result;
}

/// Processes an assignation of sets to the given permutation of numbers.
void ProcessAssignation(std::vector<Category> const& assigned_set, std::vector<int> const& numbers)
{
    // So far we have complexity \Theta(n! * 4^n).

    // Now, we will only consider the set assignation valid if it is sorted, i.e. we have first
    // all the "Nothing", then all then "DivisibleBy3", and so on. This will not dominate the asymptotic cost,
    // so no reason to be stupid.
    bool is_sorted = true;
    for (std::size_t i = 1; i < assigned_set.size(); ++i)
        is_sorted = is_sorted && assigned_set[i - 1] <= assigned_set[i];

    if (!is_sorted)
        return;

    // Now that we now that the sets make sense with our restrictions, check that the assignation is correct.
    bool is_assignation_correct = true;
    for (std::size_t i = 0; i < assigned_set.size(); ++i)
        is_assignation_correct = is_assignation_correct && IsAssignationCorrect(assigned_set[i], numbers[i]);

    if (!is_assignation_correct)
        return;

    // We have a valid assignation of the numbers, and they are sorted by groups. However, we only accept the permutation
    // if the numbers themselves are sorted within each group.
    bool are_numbers_sorted = true;
    for (std::size_t i = 1; i < assigned_set.size(); ++i)
    {
        if (assigned_set[i - 1] == assigned_set[i])
            are_numbers_sorted = are_numbers_sorted && numbers[i - 1] < numbers[i];
    }

    if (!are_numbers_sorted)
        return;

    // Now print them, but we want them sorted, so we need to sort them first. But let us sort them by trying each possible permutation.
    std::vector<std::pair<int, Category>> output(assigned_set.size());
    for (std::size_t i = 0; i < output.size(); ++i)
        output[i] = std::make_pair(numbers[i], assigned_set[i]);

    // This dominates the cost of this function, being \Theta(n!). Thus, the total cost of the algorithm is \Theta((n!)^2 * 4^n).
    while (std::next_permutation(output.begin(), output.end())) { }

    for (auto const& [x, category] : output)
    {
        switch (category)
        {
            case Category::Nothing:
                std::cout << x << std::endl;
                break;
            case Category::DivisibleBy3:
                std::cout << "Fizz" << std::endl;
                break;
            case Category::DivisibleBy5:
                std::cout << "Buzz" << std::endl;
                break;
            case Category::DivisibleBy3And5:
                std::cout << "FizzBuzz" << std::endl;
                break;
        }
    }
}

/// Backtracking that assigns one category to each element of @p assigned_set with index greater or equal than @p current_index.
void AssignSets(std::size_t current_index, std::vector<Category>& assigned_set, std::vector<int> const& numbers)
{
    if (current_index == assigned_set.size())
    {
        // We reached a complete assignation, so process it.
        ProcessAssignation(assigned_set, numbers);
        return;
    }

    // Assign each possible category.
    for (std::size_t i = 0; i < 4; ++i)
    {
        assigned_set[current_index] = static_cast<Category>(i);
        AssignSets(current_index + 1, assigned_set, numbers);
    }
}

int main(int argc, char** argv)
{
    if (argc < 2)
    {
        std::cout << "Usage: executable n" << std::endl;
        return 0;
    }

    int n = std::atoi(argv[1]);

    // Start by pushing the numbers to a vector.
    std::vector<int> numbers(n);
    std::generate(numbers.begin(), numbers.end(), [i = n] () mutable { return i--; });
    std::random_shuffle(numbers.begin(), numbers.end());

    // Iterate through all the permutations of the vector: \Theta(n!)
    uint64_t n_factorial = ComputeFactorial(n);
    for (uint64_t i = 0; i < n_factorial; ++i)
    {
        std::next_permutation(numbers.begin(), numbers.end());

        // Now we want to assign each number to one of the possible 4 groups:
        // nothing, divisible by 3, divisible by 5, divisible by 3 and 5.
        // This takes \Theta(4^n) without considering what we will be doing once each assignation is computed.
        std::vector<Category> assigned_set(n);
        AssignSets(/*current_index*/ 0, assigned_set, numbers);
    }
}