SPOJ Brasil

Um palíndrome é uma sequência de caracteres que formam a mesma palavra quando lida tanto lida da esquerda para a direita quanto lida da direita para a esquerda. Por exemplo, reter e arra são palíndromes. Segundo essa definição, qualquer sequência comum único caractere também é um palíndrome.

Dado um alfabeto S de caracteres distintos e um inteiro K, podemos enumerar todos os possíveis palíndromes de tamanho K usando caracteres do alfabeto dado. Por exemplo, se S = {a, b, x} e K = 3 temos, em ordem alfabética, os palíndromes aaa, aba, axa, bab, bbb, bxb, xax, xbx, xxx. Ou seja, há 9 palíndromes possíveis.

Podemos atribuir um índice a cada um desses palíndromes, nessa ordem, iniciando de 1. Sendo assim, o palíndrome 4 seria bab no exemplo dado.

Tarefa

Escreva um programa que, dados o alfabeto S de caracteres distintos, o inteiro K e o índice I, retorne o I-ésimo palíndrome de tamanho K usando apenas os caracteres do alfabeto dado.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém um inteiro N (2 ≤ N ≤ 26) indicando o tamanho do alfabeto. A segunda linha contém uma string S com os caracteres do alfabeto. O alfabeto consiste apenas de caracteres minúsculos (de a a z), todos distintos e já ordenados. A terceira linha contém dois inteiros, K (3 ≤ K ≤ 100) e I (1 ≤ I ≤ 10¹⁸), separados por um espaço em branco. O valor de I sempre será válido, ou seja, nunca será mais alto que a quantidade de palíndromes possíveis de tamanho K usando o alfabeto S.

Saída

Seu programa deve imprimir, na saída padrão, uma única linha, contendo o I-ésimo palíndrome de tamanho K usando o alfabeto S.

Exemplo

Entrada:
3
abx
3 4

Saída:
bab

Entrada:
3
ert
5 12

Saída:
reter

Entrada:
10
abcdefghij
8 11

Saída:
aabaabaa