A Alice adora brincar com o seu filhote. Um dos seus brinquedos favoritos são os blocos numéricos, uns pequenos cubos de madeira com dígitos inscritos. O filho adora empilhar os blocos uns por cima dos outros formando uma enorme pilha de blocos! E fica ainda mais contente quando de seguida a mãe desfaz a pilha de blocos para formar um único número.
Este número é criado dígito a dígito. De cada vez, a Alice retira o bloco que está no topo da pilha e junta-o ao lado esquerdo ou direito do número que está a formar. A figura seguinte exemplica uma pilha de quatro blocos alguns dos números que se podiam obter: 3854, 3845 e 4583. Nota que existiam ainda outros números que podiam ser formados com a mesma pilha.
Para tornar as coisas mais interessantes, a Alice pensa num outro número e tenta obtê-lo a partir da pilha. Se não o conseguir, procura obter um número próximo. Mais especificamente, se ela pensar num número N, procura obter o menor número que seja maior ou igual a N. Por exemplo, para o número 4000 e a pilha de blocos da imagem anterior, o menor número maior ou igual a 4000 é o 4583. Se N fosse 8000, então o número que se consegue obter é o 8453.
Como uma mesma pilha pode dar origem a tantos números diferentes, não é fácil para a Alice descobrir o número desejado. Tens de ajudá-la!
Dado o conteúdo de uma pilha de B blocos com dígitos, e um número N, a tua tarefa é descobrir qual o menor número maior ou igual a N que se consegue formar.
A primeira linha contém um número inteiro B, o número de blocos na pilha. A segunda linha representa a pilha de blocos, começando pelo topo, com B dígitos (algarismos de zero a nove). A terceira linha representa o número N, constituído por B dígitos.
O output é constituído por uma única linha, indicando o menor número maior ou igual a N que se pode obter usando todos os blocos da pilha, ou a palavra "NENHUM", se não existir nenhum número possível nestas condições.
Nota que podem existir zeros à esquerda do número.
São garantidos os seguintes limites em todos os casos de teste:
1 ≤ B ≤ 200 | Número de blocos na pilha |
Para um conjunto de casos de teste valendo 30% dos pontos, acontece sempre que B ≤ 7.
Para um conjunto de casos de teste valendo 50% dos pontos, acontece sempre que B ≤ 20.
Para um conjunto de casos de teste valendo 20% dos pontos, 50 ≤ B ≤ 200, mas o número N contém apenas zeros.
4 5483 4000
4583
3 371 900
NENHUM
4 0801 0004
0081