Unique Xi Stone Dictionary

A Xi‑n‑k magical stone is a granite tablet with exactly n letters, each of which is either I or X. Moreover, the tablet contains at most k pairs of adjacent letters that are different (i.e. one letter is I and the other is X). Formally, for a string s of length n, let its transition count be defined as

$$\text{trans}(s)=\sum_{j=1}^{n-1} [s_j \neq s_{j+1}], $$

where \([\cdot]\) is the Iverson bracket. The condition is trans(s) \le k.

Another twist is that the stone can be rotated by 180° (which reverses the string). Two inscriptions are considered to be the same stone if one is equal to the reverse of the other. If a stone can be read in two different ways, its canonical reading is defined as the lexicographically smaller between its inscription and its reversed inscription. For a symmetric stone (where the inscription is invariant under 180° rotation) there is only one reading.

For example, consider the case n=3, k=2. The six valid canonical readings in lexicographical order are:

III
IIX
IXI
IXX
XIX
XXX

Given n, k and an index i, your task is to determine the i-th inscription in the lexicographically sorted dictionary of canonical readings for a Xi‑n‑k magical stone.

inputFormat

The input consists of three integers n, k and i (1-indexed), separated by spaces or newlines.

Constraints: It is guaranteed that 1 ≤ n ≤ 18 and 0 ≤ k < n. You may assume the provided i is valid (i.e. there exists an answer).

outputFormat

Output the canonical reading (a string of length n composed of only the characters I and X) that appears in the i-th position in the lexicographically sorted dictionary.

sample

3 2 1

III