Word

Time limit2sMemory limit512 MB

Summary

Find the k-th word in lexicographic order among words of length at most n over letters a, b, c with no two equal adjacent letters, or report that fewer than k exist.

Level: Medium6 of 10
Topics: Combinatorics, Math, Greedy, Implementation
Solved: No attempts yet

Problem

Find the k-th word in lexicographic order among the nonempty words that consist of at most n letters from the set {a, b, c} and in which every two adjacent letters are different.

Recall that a word s is smaller than a word t (s ≠ t) in lexicographic order if s is a prefix of t, or if at the first position where s and t differ, the letter in s is earlier in the alphabet than the letter in t.

Input

The only line of input contains two integers n and k. (1 ≤ n ≤ 106, 1 ≤ k ≤ 1018)

Output

If fewer than k words satisfy the conditions, print NIE. Otherwise, print the requested word in a single line.

Examples2

Example 1
Input
```
3 7
```
Expected output
```
acb
```
Example 2
Input
```
2 10
```
Expected output
```
NIE
```