Codificación aritmética P37123

Considera un alfabeto $\Sigma$ donde cada letra $c_i$ tiene asociado una probabilidad $p_i$. Por ejemplo, $\Sigma=\{c_1=A, c_2=B, c_3=C\}$ con $$p(A) = p_1 = \frac{1}{2}, \qquad p(B) = p_2 = \frac{1}{5} \qquad p(C) = p_3 = \frac{3}{10}$$ A cada palabra (secuencia de letras) $s$ del alfabeto $\Sigma$ le asignamos un intervalo $I(s)=[a;b)$ según las reglas siguientes.

• El intervalo de la palabra vacía $s=\lambda$ es $$I(\lambda)=[0; 1).$$

• El intervalo de la palabra $s=t\cdot c_i$, donde $t$ es una palabra con $I(t)=[a; b)$ y $c_i$ es la última letra de $s$, es $$I(s)=[a + (p_1 + \cdots + p_{i-1})\cdot(b-a); a + (p_1 + \cdots + p_i)\cdot(b-a)).$$

Por ejemplo, a las palabras $\lambda$, $\texttt{A}$, $\texttt{AA}$, $\texttt{AAC}$, $\texttt{AACB}$ les corresponden los siguientes intervalos: $$\begin{align*} I(\lambda) &= [0; 1) \\ I(A) &= [0 + 0\cdot 1; 0 + 0.5 \cdot 1) = [0; 0.5) \\ I(AA) &= [0 + 0 \cdot 0.5; 0 + 0.5 \cdot 0.5) = [0; 0.25) \\ I(AAC) &= [0 + 0.7 \cdot 0.25; 0 + 1 \cdot 0.25) =[0.175; 0.25) \\ I(AACB) &= [0.175 + 0.5 \cdot 0.075; 0.175 + 0.7 \cdot 0.075) = [0.2125; 0.2275) \end{align*}$$ Cuantas más letras añadimos, más pequeño es el intervalo resultante.

Entrada

Una línea con el número $n$ de letras del alfabeto. A continuación, $n$ líneas con las letras $c_i$ del alfabeto y las probabilidades $p_i$ de cada letra. Todas las probabilidades cumplen $p_i\ge 0.1$ y se te garantiza que $p_1 + \cdots + p_n = 1$.

Por último, un número indeterminado de líneas con los casos de prueba. Cada caso de pruebas es un número natural $k<6$ y un número real $r$ entre $0$ y $1$.

Salida

Para cada caso, escribe la única palabra $s$ de $k$ letras cuyo intervalo $I(s)$ contiene el real $r$. Se te garantiza que las entradas serán tales que nunca tendrás problemas de precisión usando double.