XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: festa.x, onde x deve ser c, cpp, java, js ou py

Festa olímpica

Os atletas da Nlogônia obtiveram o melhor resultado do país em olimpíadas, e para comemorar o rei decidiu dar uma grande festa no Palácio Real. Todos os atletas foram convidados, mas o rei quer também convidar alguns de seus súditos.

Como não é possível convidar todos os súditos, o rei determinou que a seguinte Lei seja utilizada para calcular a lista de convidados:

Lei Especial Sobre Comemoração das Olimpíadas

Por ordem de Sua Majestade, fiquem todos sabendo que:
  • Os N súditos de Nlogônia serão numerados 1, 2, 3, …, N e uma lista ordenada será criada com os números dos súditos. A primeira posição da lista será 1.
  • Um número M de turnos serão então executados; em cada turno i, será sorteado um número Ti que será usado para remover súditos da lista, da seguinte forma: no turno i, devem ser removidos da lista todos os súditos que ainda continuam na lista e que ocupam posições que são múltiplas de Ti; ou seja, devem ser removidos os súditos que estão nas posições (Ti, 2Ti, 3Ti, …) da lista corrente. Ao final do turno, para não haver posições vazias na lista (cujos súditos foram removidos) a lista é reagrupada, mantendo-se a mesma ordem relativa, e contendo apenas os números dos súditos remanescentes.

  • Os súditos que permanecerem na lista ao final dos M turnos serão convidados para a grande festa de comemoração do resultado das olimpíadas.

Dados o número de súditos e os números sorteados em cada turno, sua tarefa é determinar os súditos que serão convidados de acordo com a Lei Especial.

Entrada

A primeira linha da entrada contém um número inteiro N, o número de súditos de Nlogônia. A segunda linha contém um inteiro M, o número de turnos. Cada uma das M linhas seguintes contém um inteiro Ti, o número que foi sorteado para o turno i.

Saída

Seu programa deve produzir a lista de convidados de acordo com a Lei Especial, com uma linha para cada convidado, cada linha contendo somente o número de um convidado. Como a lista total dos convidados pode ser muito grande, o rei ordenou que, caso o número de convidados seja maior que 10.000, você deve listar apenas os 10.000 primeiros (ou seja, os com menores números) convidados.

Restrições

  • 2 ≤ N ≤ 1 000 000 000
  • 1 ≤ M ≤ 5 000
  • 2 ≤ Ti ≤ 100 000 para 1 ≤ i ≤ M

Informações sobre a pontuação

  • Para um conjunto de casos de testes valendo 17 pontos, N ≤ 100 e M ≤ 10.
  • Para um conjunto de casos de testes valendo outros 22 pontos, N ≤ 400 000 e M ≤ 5 000.
  • Para um conjunto de casos de testes valendo outros 21 pontos, Ti = 2 para 1 ≤ i ≤ M.
  • Para um conjunto de casos de testes valendo outros 40 pontos, nenhuma restrição adicional.

Exemplos

Entrada
10
2
2
3
Saída
1
3
7
9
	

 

Entrada
6
3
2
2
2
Saída
1
	

 

Entrada
5
1
10
Saída
1
2
3
4
5
	

 

Entrada
1000000
3
2
15
3
Saída
1
3
7
9
...
32137
32139
	

 

Tarefas Programação Nível 2
Promoção
logo sbc
Patrocínio
Apoio
Coordenação