#5191. 「PA 2016」Słowo

标签: 传统 | 时间限制: 1000 ms | 内存限制: 256 MiB |

题目描述

题目译自 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