1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <iostream>
#include <cstdint>

uint_fast64_t get_num_words_left(uint_fast64_t n) {
	uint_fast64_t one = 1;
	return (one << n) - 1;
}

char get_next(char last, int which) {
	char next[3][2] = {{'b', 'c'}, {'a', 'c'}, {'a', 'b'}};
	return next[last - 'a'][which];
}

void update_initial(std::string &buffer, uint_fast64_t n_limit,
	uint_fast64_t &n, uint_fast64_t &k) {
	
	char last = 'b';
	for(; n >= n_limit && k > 0; --n, --k) {
		last = get_next(last, 0);
		buffer.push_back(last);
	}
}

void update_reminder(std::string &buffer, uint_fast64_t &n, uint_fast64_t &k) {
	uint_fast64_t num_words;
	// The buffer is assumed to be non-empty
	char last = *buffer.rbegin();
	
	for(; n > 0 && k > 0; --n, --k) {
		num_words = get_num_words_left(n);
		if(k > num_words) {
			last = get_next(last, 1);
			k -= num_words;
		} else {
			last = get_next(last, 0);
		}
		buffer.push_back(last);
	}	
	
}

void print_nth_word(uint_fast64_t n, uint_fast64_t k) {
	std::string buffer;
	// There are 3 * (2^n - 1) words of length n
	// "NIE" is only possible for n < 59
	// Take 62 here just fpor safety both ways
	uint_fast64_t n_limit = 62;

	// k can exceed number of words for n
	if(n <= n_limit) {
		uint_fast64_t num_words = get_num_words_left(n);
		if(k > 3 * num_words) {
			std::cout << "NIE" << std::endl;
			return;
		}
		// The first lettre is 'c'
		else if(k > 2 * num_words) {
			buffer.push_back('c');
			k -= 2 * num_words + 1;
		}
		// The first lettre is 'b'
		else if(k > num_words) {
			buffer.push_back('b');
			k -= num_words + 1;
		}
		// The first lettre is 'a'
		else {
			buffer.push_back('a');
			k -= 1;
		}
		n--;
	}
	// k is smaller than the number of words for n
	else {
		update_initial(buffer, n_limit, n, k);
	}
	update_reminder(buffer, n, k);

	std::cout << buffer << std::endl;
}

int main() {
	uint_fast64_t n;
	uint_fast64_t k;

	std::cin >> n >> k;

	print_nth_word(n, k);

	return 0;
}