Legible Words II X81292

In computer science we often consider words made of letters. Again, we define that a word is legible iff there are no three consecutive consonants.

You have already calculated the number of legible words of given length. But now you feel that simply counting the words is not enough. Your new challenge is to calculate the $i$-th of these words, according to the Measharan alphabet.

Input

Input consists of several cases. Each case consists of three lines: $W$ (the string of all letters in the Measharan alphabet), $T$ (the types of all letters in $W$), $N\ \ I$ (where $N$ the length of the words to consider, and $I$ is the index of the word to output).

$W_1$ is the first letter in the alphabet, $W_2$ is the second, and so on. $T_i$ is c iff $W_i$ is a consonant, and v iff $W_i$ is a vowel. Each letter is encoded as a lowercase letter of the English alphabet (a..z).

As in Legible Words, it is guaranteed that the total number of $N$-letter words will never be greater than $10^{18}$, and $1 \leq N \leq 100$.

After the last case the input contains a line containing only 0.

Output

Output the $i$-th $N$-letter legible word, according to the lexicographic ordering (if we have two words $u$, $v$ such that $u_1 u_2 \ldots u_k = v_1 v_2 \ldots v_k$, and $u_{k+1} \neq v_{k+1}$, and $u_{k+1}$ comes before $v_{k+1}$ in $W$, then $u$ is before $v$ in the lexicographic ordering).