[BalticOI 2008] 魔法石

题目描述

知名的石头 $\text{Xi-n-k}$ 只能在 Wonderland 中找到,这样的石头只是一种碑文只有字母 ``X`` 和 ``I`` 的花岗岩板。每个石板包含 $n$ 个字母。每个石板上有不超过 $k$ 个位置 ``X`` 和 ``I`` 相邻。 石板的顶部和底部不是固定的,所以石头可以旋转,变为倒立状态。例如下面这两个图片描述的是一样的石头。 ![0](https://i.loli.net/2018/02/20/5a8ba0ad731f2.png) (看同样石头的两种方式。这种石头的种类是 $\text{Xi-8-3}$,也是 $\text{Xi-8-4}$(当然也可以是 $\text{Xi-8-}k$,$k \ge 3$))。 现在 Wonderland 中任意两块魔法石都不是一样的,即两块石头都没有相同的碑文(注意旋转 $180^\circ$​​ 是允许的)。 如果可以以两种不同方式(用旋转 $180^\circ$​​ 的方式)读一块石头的碑文,那么对于这块石头,碑文的正规阅读方式被定义为两种阅读方式字典序小的那种。 如果一块石头的碑文是对称的,即旋转 $180^\circ$​​ 并不改变碑文,那么对于这块石头,碑文的的正规阅读方式被定义为这种独一无二的阅读方式。 例如:有六种 $\text{Xi-3-2}$ 魔法石,它们的正规阅读方式以字典序写出为:``III``,``IIX``,``IXI``,``IXX``,``XIX`` 和 ``XXX``。 Alice 是一个研究 Wonderland 的魔法石的专家。她想要创建一个 $\text{Xi-n-k}$ 魔法石的正规阅读方式字典(对于一些特定的 $n$ 和 $k$)。对于给出的 $i$,在字典中第 $i$ 个位置应该是什么碑文呢? #任务 写一个程序能够: - 从标准输入中读取数字 $n$,$k$,$i$ - 判定对于 $\text{Xi-n-k}$ 魔法石,第 $i$ 个正规阅读方式(按字典序) - 输出结果到标准输出

输入输出格式

输入格式


标准输入只有一行,包含三个数 $n$,$k$,$i$,用一个空格分开。

输出格式


标准输出只有一行,应该包含 $\text{Xi-n-k}$ 魔法石,第 $i$ 个正规阅读方式(按字典序)。 如果 $\text{Xi-n-k}$ 魔法石的数量比 $i$ 小,那么只输出一行一个短语 ``NO SUCH STONE``。

输入输出样例

输入样例 #1

3 2 5

输出样例 #1

XIX

输入样例 #2

3 2 7

输出样例 #2

NO SUCH STONE

说明

**数据范围与提示** 对于全部数据,$0\le k<n\le 60,0<i<10^{18}$​​。 注:我们说 $\text{A}$ 的碑文字典序比 $\text{B}$ 小(假设 $\text{A}$ 和 $\text{B}$ 的碑文长度相同),当且仅当在第一个碑文不同的位置 $\text{A}$ 包含 ``I`` 且 $\text{B}$ 包含 ``X`` 。