题目描述

题目译自 PA 2016 Runda próbna Słowo

本任务要求找出在字典序中第 $k$ 个非空单词，这些单词由最多 $n$ 个字母组成，字母取自集合 $\{\texttt{a}, \texttt{b}, \texttt{c}\}$，且单词中任意两个相邻字母必须不同。

提醒一下，在字典序中，单词 $s$ 小于单词 $t$ $(s \neq t)$ 的条件是：$s$ 是 $t$ 的前缀，或者在 $s$ 和 $t$ 第一个不同的位置上，$s$ 中的字母在字母表顺序中小于 $t$ 中的字母。

输入格式

输入一行包含两个整数 $n$ 和 $k$ $(1 \leq n \leq 10^{6}, 1 \leq k \leq 10^{18})$，如题目描述中定义。

输出格式

如果满足任务条件的单词总数少于 $k$，则输出 NIE。否则，输出一行一个字符串，表示所求的单词。

3 7

acb

2 10

NIE