L. LC BB ND CNDY
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Fingers on buzzers teams, it's time for the Missing Vowels Round. In this game, we've taken famous words, phrases, or sayings, removed the vowels, and then re-spaced the consonants.

So for example, for the category "Sports for nerds," the clue might be,

CMPT TVPR GRM MNG
and the answer is,
COMPETITIVE PROGRAMMING
For the category "A poet, a peninsula, and a pronoun", the clue might be,
LC BB ND CNDY
and the answer is, obviously,
LACABA, BONDOC, AND YOU

Alice, Bob, and Cindy are training for their appearance on Only Connect (their team name is "The Github Heatmappers"), and in particular they would like to train for the Missing Vowels Round. They ask for your help in creating a program that allows them to train.

As a formalization of the rules given above, in the Missing Vowels Round, the following transformation is applied to a string:

  • First, remove all characters that aren't consonants, but preserve the order of these consonants.
    • Y is always considered a consonant for this problem
  • Capitalize all these consonants
  • You may insert spaces anywhere in the remaining letters, so long as when you're done...
    • The phrase does not begin or end in a space.
    • There are no two consecutive spaces anywhere
Let $$$\mathcal{L}(s)$$$ be the list of all possible strings that can be achieved by this process, given some starting string $$$s$$$, sorted in lexicographic order (note that the "space" character comes comes before all letters of the alphabet; see the Notes for an explanation of lexicographic ordering). Given $$$i$$$ and some string $$$s$$$, what is the $$$i$$$th element of $$$\mathcal{L}(s)$$$? Also, if $$$\mathcal{L}(s)$$$ has fewer than $$$i$$$ elements, you should say so as well.
Input

The first line of input contains the string $$$s$$$, which may contain whitespaces.

The second line of input contains a single integer $$$i$$$.

Output

If $$$\mathcal{L}(s)$$$ has fewer than $$$i$$$ elements, output the phrase "out of bounds" (without the quotes; note it is in all-lowercase), Otherwise, output the $$$i$$$th element in $$$\mathcal{L}(s)$$$.

Scoring

$$$$$$\begin{align*}

&\begin{array}{|l|} \hline \text{Constraints For All Subtasks} \\ \hline 1 \leq i \leq 10^{18} \\ 1 \leq |s| \leq 2 \times 10^5 \\ \text{$s$ consists of upper and lowercase letters, punctuation }\mathtt{,.!?}\text{ and spaces.} \\ \text{$s$ does not begin or end in a space, and it has no two consecutive spaces.} \\ \text{$s$ contains at least one consonant.} \\ \hline \end{array}\\

&\begin{array}{|c|c|l|} \hline \text{Subtask} & \text{Points} & \text{Constraints} \\ \hline 1 & \mathbf{40} & |s| \leq 15 \\ \hline 2 & \mathbf{40} & i \leq 2 \times 10^5 \\ \hline 3 & \mathbf{20} & \text{No further constraints.} \\ \hline \end{array}\\

\end{align*}$$$$$$

Examples
Input
NOI.PH
3
Output
NP H
Input
Alice, Bob, and Cindy
344
Output
LC BB ND CNDY
Input
Who Lives, Who Dies, Who Tells Your Story
1000000000000000000
Output
out of bounds
Input
!B
1
Output
B
Note

Comparison operators like < are actually defined on strings in almost all programming languages. Try it!

They are defined in a way consistent with "dictionary ordering". Suppose we have two strings $$$s$$$ and $$$t$$$ such that $$$s \neq t$$$.

  • Let $$$i$$$ be the smallest index such that $$$s_i \neq t_i$$$ (i.e. "the first place where the two strings differ")—then, $$$s \lt t$$$ if and only if $$$s_i \lt t_i$$$ (e.g. cash comes before cave because s < v).
  • If no such $$$i$$$ exists, then one is a prefix of the other word, and by convention, the prefix comes first (e.g. cat comes before caterwaul).
As for how to compare characters, their ordering is determined by getting its equivalent ASCII code and comparing the integers. For this problem, all you need to know is that the letters are in fact sorted in alphabetical order, and the space character comes before all letters.

So, for example, "LIL MAN" (without the quotes) comes before LILAC because the two strings first differ at their fourth character, and there, the space precedes A in ASCII ordering.