Trechos de uma mensagem
Uma mensagem é descrita por uma expressão compacta. Letras minúsculas representam a si mesmas; expressões lado a lado são concatenadas; k[expressão] significa repetir a expressão interna exatamente vezes. Por exemplo, ab3[c2[d]] representa abcddcddcdd.
As expressões dentro de colchetes nunca são vazias. Cada número aparece imediatamente antes de [, não tem zeros à esquerda e está entre 1 e . Os colchetes são balanceados. A expressão inteira contém pelo menos uma letra após a expansão.
Responda a consultas que pedem um trecho da mensagem expandida, sem precisar construir toda essa mensagem. As posições começam em 1 e ambos os extremos pertencem ao trecho.
Input
A primeira linha contém a expressão , sem espaços. A segunda contém . Cada uma das próximas linhas contém e .
- ;
- no máximo 30 pares de colchetes podem estar abertos simultaneamente;
- o comprimento da mensagem expandida é no máximo ;
- e ;
Output
Para cada consulta, imprima o trecho solicitado em uma linha.
Samples
Sample 1
Input
ab3[c2[d]] 3 1 5 4 9 11 11
Output
abcdd ddcddc d
A mensagem expandida é abcddcddcdd. Cada consulta usa as posições dessa mensagem, não da expressão compacta.