著名的 Xi-n-k 石头只能在奇境(Wonderland)中找到。这样的一块石头实际上是一块花岗岩板,上面刻有仅由字母 X 和 I 组成的铭文。每块板上恰好有 $n$ 个字母。在每块板中,字母 X 和 I 相邻的位置不超过 $k$ 处。
石头的上下两面没有固定,因此石头可以颠倒旋转(即首尾翻转)。例如,下面两幅图描绘的是完全相同的石头:
IXXIIXXX XXXIIXXI
图 1:看同一块石头的两种方式。这块石头的类型是 Xi-8-3,但也是 Xi-8-4(以及任何 $k \ge 3$ 的 Xi-8-k 类型)。
奇境中没有两块魔法石头是相同的,也就是说,没有两块石头包含相同的铭文(请记住,石头允许颠倒旋转)。
如果可以通过两种不同的方式(利用颠倒旋转)来读取某块石头的铭文,那么该石头的标准表示(canonical representation)定义为这两种读取方式中字典序较小*的那一个。
如果一块石头的铭文是对称的,即颠倒旋转不会改变它,那么它的标准表示就定义为读取该铭文的唯一方式。
* 我们称铭文 $A$ 在字典序上小于 $B$(假设 $A$ 和 $B$ 长度相同),如果在它们第一个不同的位置上,$A$ 包含字母 I 且 $B$ 包含字母 X。
示例:恰好有 6 块类型为 Xi-3-2 的石头。按字典序排列,它们的标准表示依次为:III,IIX,IXI,IXX,XIX 和 XXX。
爱丽丝是奇境中 Xi-n-k 石头方面的著名专家。她想为所有类型为 Xi-n-k 的石头(对于给定的 $n$ 和 $k$)的标准表示建立一个字典序索引。
对于给定的 $i$ 值,索引中第 $i$ 个位置应该写什么铭文?
请编写一个程序:
- 从标准输入读取数字 $n$,$k$ 和 $i$,
- 确定类型为 Xi-n-k 的石头按字典序排列的第 $i$ 个标准表示,
- 将结果写入标准输出。
输入格式
输入只有一行,包含三个整数 $n$,$k$ 和 $i$($0 \le k < n \le 60$,$0 < i < 10^{18}$),它们之间用单个空格分隔。
输出格式
输出只有一行,包含类型为 Xi-n-k 的石头按字典序排列的第 $i$ 个标准表示。
如果 Xi-n-k 石头的数量少于 $i$,则输出唯一的一行应包含 NO SUCH STONE。
样例
输入样例 1
3 2 5
输出样例 1
XIX
输入样例 2
3 2 7
输出样例 2
NO SUCH STONE