$N$ vacas $(1 \le N \le 50,000)$ numeradas por conveniência $1..N$ aprendem criptografia. Estudados exemplos, criam a própria! Sem experiência, o algoritmo é simples:
Cada vaca $i$ recebe início $C_i$ $(0 \le C_i < 90,000,000)$; todas fazem em paralelo:
- Primeiro, cada uma soma os números das outras $N-1$ vacas.
- Terminadas todas, cada uma substitui seu número pela soma calculada. Evitam números grandes guardando resto módulo $98,765,431$.
Em novembro contaram ao alce Canmuu, impressionado.
Numa véspera de Natal com neblina, Canmuu disse:
“Muito fácil de quebrar! Repitam $T$ vezes $(1 \le T \le 1,414,213,562)$.”
Frustradas com tantas repetições do mesmo algoritmo tedioso, após horas discutindo com Canmuu acordaram: você calcula os números após criptografia!
*As primeiras 10 submissões receberão informação extra.
Entrada
Leia entrada padrão.
- Linha 1: inteiros $N$, $T$ separados por espaço.
- Linhas $2..N+1$: linha $i+1$, um inteiro $C_i$.
Saída
Escreva na saída padrão.
- Linhas $1..N$: linha $i$, um inteiro, número da vaca $i$ ao terminar, módulo $98,765,431$.
Exemplos
Entrada 1
3 4 1 0 4
Saída 1
26 25 29
Nota
Três vacas, iniciais $1$, $0$, $4$, quatro repetições.
Tabela dos números por rodada:
| Rodada | Vaca $1$ | Vaca $2$ | Vaca $3$ |
|---|---|---|---|
| $0$ | $1$ | $0$ | $4$ |
| $1$ | $4$ | $5$ | $1$ |
| $2$ | $6$ | $5$ | $9$ |
| $3$ | $14$ | $15$ | $11$ |
| $4$ | $26$ | $25$ | $29$ |
Créditos: Neal Wu, 2007