Description

The famous stone $\text{Xi-n-k}$ can only be found in Wonderland. Such a stone is a granite slab engraved with an inscription consisting only of the letters X and I. Each slab contains $n$ letters. On each slab, there are at most $k$ positions where X and I are adjacent.

The top and bottom of a slab are not fixed, so the stone can be rotated and become upside down. For example, the following two pictures describe the same stone.

【Two ways to view the same stone. This stone is of type $\text{Xi-8-3}$, and also $\text{Xi-8-4}$ (of course it can also be $\text{Xi-8-}k$, $k \ge 3$).】

Now, in Wonderland, no two magic stones are the same, meaning that no two stones have the same inscription (note that a $180^\circ$ rotation is considered the same).

If a stone’s inscription can be read in two different ways (by rotating it $180^\circ$), then the standard way to read the inscription is defined as the lexicographically smaller of the two readings.

If a stone’s inscription is symmetric, meaning that rotating it $180^\circ$ does not change the inscription, then the standard way to read the inscription is defined as this unique reading.

For example, there are six kinds of $\text{Xi-3-2}$ magic stones. Their standard readings, written in lexicographical order, are: III, IIX, IXI, IXX, XIX, and XXX.

Alice is an expert in studying magic stones in Wonderland. She wants to create a dictionary of standard readings of $\text{Xi-n-k}$ magic stones (for some given $n$ and $k$). For a given $i$, what inscription should be at position $i$ in this dictionary?

Task

Write a program that:

• reads integers $n$, $k$, $i$ from standard input;
• determines the $i$-th standard reading (in lexicographical order) among $\text{Xi-n-k}$ magic stones;
• outputs the result to standard output.

Input Format

The standard input contains only one line with three integers $n,k,i$, separated by a single space.

Output Format

The standard output contains only one line, which should be the $i$-th standard reading (in lexicographical order) of $\text{Xi-n-k}$ magic stones.

If the number of $\text{Xi-n-k}$ magic stones is smaller than $i$, output one line with the phrase NO SUCH STONE.

3 2 5

XIX

3 2 7

NO SUCH STONE

Hint

Constraints and Hints

For all data, $0\le k<n\le 60$, $0<i<10^{18}$.

Notes

Note: We say the inscription of $\text{A}$ is lexicographically smaller than that of $\text{B}$ (assuming they have the same length) if and only if at the first position where they differ, $\text{A}$ contains I and $\text{B}$ contains X.

Translated by ChatGPT 5