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 <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <cstdlib>
#include <ctime>
#include <deque>
using namespace std;

long long k;
long long s[100];
char ss[9] = {' ', 'F', 'E', 'S', 'T', 'I', 'V', 'A', 'L'};
vector <int> Check;
vector <long long> num;
string ans;
int sspp[10000];

int main() {
	// cin >> k;
	int tot; 
	s[0] = 1;
	for (int i = 1; i <= 7; i++)
		s[i] = 1, ans.push_back(ss[i]);
	tot = 3000;
	int RND = 0;
	Check.push_back(ans.size());
	num.push_back(s[7]);
	while (tot > 0) {
		RND += 1;
		if (RND < 7)
		for (int j = 7 - RND + 1; j <= 7; j++)
			for (int i = 1; i <= 4 + RND; i++)
					s[j] += s[j - 1], tot -= 1, ans.push_back(ss[j]);
		else
			for (int j = 1; j <= 7; j++)
				for (int i = 1; i <= 4 + RND; i++)
						s[j] += s[j - 1], tot -= 1, ans.push_back(ss[j]);
		// RND += 1;
		// cout << ans << endl;
		Check.push_back(ans.size());
		num.push_back(s[7]);
		// printf("%lld %lf\n", s[7], log(s[7]) / log(10));
	}

	for (int j = 1; j <= 200; j++)
		s[6] += s[5], ans.push_back(ss[6]);
	for (int j = 1; j <= 200; j++)
		s[7] += s[6], ans.push_back(ss[7]);
	Check.push_back(ans.size());
	num.push_back(s[7]);
	// printf("%lld %lf\n", s[7], log(s[7]) / log(10));
	// for (int i = 1; i <= n)
	cin >> k;
	for (int i = (int) num.size() - 1; i >= 0; i--) {
		// cout << num[i] << endl;
		while (k >= num[i])
			sspp[i] += 1, k -= num[i];
		// printf("%lld %d\n", num[i], sspp[i]);
	}
	int pre = 0;
	for (int i = 0; i < (int) Check.size(); i++) {
		for (int j = pre; j < Check[i]; j++)
			printf("%c", ans[j]);
		for (int j = 1; j <= sspp[i]; j++)
			printf("%c", ss[8]);
		pre = Check[i];
	}
	printf("\n");
}