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<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(long long i=0;i<(long long)(n);i++)
#define N 200000


int main() {
	char c[8000];
	vector<long long> d[8];

	f(i, 1000) {
		c[i] = 'F';
		c[1000 + i] = 'E';
		c[2000 + i] = 'S';
		c[3000 + i] = 'T';
		c[4000 + i] = 'I';
		c[5000 + i] = 'V';
		c[6000 + i] = 'A';
		c[7000 + i] = 'L';
	}
	long long b[N];
	int e[N];
	f(i, N) {
		b[i] = 0;
		e[i] = -1;
	}
	long long n, k, t, bt;
	long long x, y, z;
	long long s, ans;
	bool v = true;
	ans = 0;
	scanf("%lld", &n);
	for (int i = 1; i <= 6; i++) {
		x = 1;
		d[i].push_back(x);
		f(j, 9 * i) {
			d[i].push_back(x);
			x = x * 2;
		}
		f(j, 511)d[i].push_back(x);
	}
	x = 1;
	while (n > 0) {
		if(n%2==1)d[7].push_back(x);
		x *= 2;
		n /= 2;
	}
	f(i, 512) {
		b[i] = 1;
		if (i > 0)e[i - 1] = i;
	}
	for (int i = 1; i <= 7; i++) {
		k = 0;
		x = 0;
		bt = -1;
		t = 0;
		while (k < d[i].size()) {
			if (d[i][k] <= x) {
				e[bt] = (1000 * i) + k;
				e[(1000 * i) + k] = t;
				bt = (1000 * i) + k;
				b[(1000 * i) + k] = x;
				k++;
			}
			else {
				if ((t / 1000) == (i - 1))x += b[t];
				bt = t;
				t = e[t];
			}
		}
	}
	t = 0;
	while (t >= 0) {
		printf("%c", c[t]);
		t = e[t];
	}
	printf("\n");


	return 0;
}