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 <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <queue>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>

using namespace std;

typedef long long ll;
typedef pair<int,int> PP;

/*
    freopen("input","r",stdin);
    freopen("output","w",stdout);
*/

ll check(string s) {
    if (s.size() > 5000) return -1;
    ll DP[8];
    memset(DP, 0, sizeof(DP));
    for (int i = 0;i < s.size();i++) {
        if (s[i] == 'F') DP[0]++;
        if (s[i] == 'E') DP[1] += DP[0];
        if (s[i] == 'S') DP[2] += DP[1];
        if (s[i] == 'T') DP[3] += DP[2];
        if (s[i] == 'I') DP[4] += DP[3];
        if (s[i] == 'V') DP[5] += DP[4];
        if (s[i] == 'A') DP[6] += DP[5];
        if (s[i] == 'L') DP[7] += DP[6];
    }
    return DP[7];
}

int main() {
    ios::sync_with_stdio(false);
    ll K;
    cin >> K;
    ll DP[8];
    ll Q[8]; // Rem
    ll P[8]; // Number of Operation in second round.
    memset(DP, 0, sizeof(DP));
    memset(Q, 0, sizeof(Q));
    memset(P, 0, sizeof(P));
    DP[7] = K;
    Q[0] = 1;
    for (int i = 7;i > 0;i--) {
        if (DP[i] <= 2) {
            DP[i - 1] = DP[i];
            Q[i] = DP[i];
        }
        else {
            ll T = min(400LL, DP[i] - 1);
            bool ok = 0;
            for (int j = T;j > 0 && ok == 0;j--) {
                if (DP[i] % j != 0) {
                    Q[i] = DP[i] % j;
                    DP[i - 1] = DP[i] / j;
                    P[i] = j;
                    ok = 1;
                }
            }
        }
    }
    string s = "FESTIVAL";
    string sol = s;
    for (int i = 7;i > 0;i--) {
        for (int j = Q[i];j > 1;j--) sol.push_back(s[i]);
    }
    for (int i = 1;i < 8;i++) {
        for (int j = 0;j < P[i];j++) {
            sol.push_back(s[i]);
        }
    }
    //ll ans = check(sol);
    //if (ans != K) cerr << "WRONG" << endl;
    cout << sol << endl;
    return 0;
}