Problem: Welcome to CODE FESTIVAL 2016! In order to celebrate this contest, find a string s that satisfies the following conditions:

* The length of s is between 1 and 5000, inclusive.
* s consists of uppercase letters.
* s contains exactly K occurrences of the string "FESTIVAL" as a subsequence. In other words, there are exactly K tuples of integers (i_0, i_1, ..., i_7) such that 0 ≤ i_0 < i_1 < ... < i_7 ≤ |s|-1 and s[i_0]='F', s[i_1]='E', ..., s[i_7]='L'.



It can be proved that under the given constraints, the solution always exists. In case there are multiple possible solutions, you can output any.

Constraints

* 1 ≤ K ≤ 10^{18}

Input

The input is given from Standard Input in the following format:


K


Output

Print a string that satisfies the conditions.

Examples

Input

7


Output

FESSSSSSSTIVAL


Input

256


Output

FFEESSTTIIVVAALL

Solution (in CPP):

Solution:
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <random>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i, m, n) for (int i = (m); (i) < int(n); ++(i))
#define whole(x) begin(x), end(x)
using ll = long long;
using namespace std;

template <typename T, typename Container>
T count_festival(Container const & a) {
    array<T, 8> dp = {};
    repeat (i, a.size()) {
        if (i % 8 == 0) {
            dp[i % 8] += a[i];
        } else {
            dp[i % 8] += dp[i % 8 - 1] * a[i];
        }
    }
    repeat_from (i, 1, 8) {
        dp[i] += dp[i - 1];
    }
    return dp[7];
}
string solve(ll k) {
    array<int, 80> a = {};
    auto get_length = [&]() {
        ll cnt = count_festival<ll>(a);
        assert (cnt <= k);
        return accumulate(whole(a), 0) + (k - cnt) + 7;
    };
    default_random_engine gen;
    for (int iteration = 0; get_length() > 5000; ++ iteration) {
        int limit = iteration < 5000 ? 8 : min<int>(a.size(), 8 + iteration / 100);
        int base = limit / 8 * 8;
        int i = uniform_int_distribution<int>(0, limit - 1)(gen);
        if (base <= i) {
            i = base + 8 - (i - base) - 1;
        }
        a[i] += 1;
        if (count_festival<double>(a) > k or count_festival<ll>(a) > k) {
            a[i] -= 1;
        }
    }
    string s;
    repeat (i, a.size()) {
        s += string(a[i], "FESTIVAL"[i % 8]);
    }
    s += string(k - count_festival<ll>(a), 'F');
    s += "ESTIVAL";
    return s;
}
int main() {
    ll k; cin >> k;
    string s = solve(k);
    cout << s << endl;
    return 0;
}