$N$ mucche $(1 \le N \le 50,000)$ comodamente numerate $1..N$ imparano la crittografia. Studiati esempi, creano la propria! Inesperte, usano algoritmo semplice:
Mucca $i$ riceve iniziale $C_i$ $(0 \le C_i < 90,000,000)$, tutte eseguono in parallelo:
- Prima ognuna somma numeri delle altre $N-1$ mucche.
- Finite tutte, ciascuna sostituisce il proprio numero con la somma calcolata. Per evitare numeri grandi tengono resto modulo $98,765,431$.
A novembre raccontarono all'alce Canmuu, impressionato.
Una vigilia di Natale nebbiosa, Canmuu disse:
«Troppo facile violarlo! Ripetete $T$ volte $(1 \le T \le 1,414,213,562)$».
Frustrate dalle tante ripetizioni dello stesso algoritmo noioso, dopo ore di litigi con Canmuu giunsero al compromesso: tu calcoli i numeri dopo crittografia!
*Le prime 10 submission riceveranno informazioni aggiuntive.
Input
Leggi ingresso standard.
- Riga 1: interi $N$, $T$ separati da spazio.
- Righe $2..N+1$: riga $i+1$, un intero $C_i$.
Output
Scrivi sull'uscita standard.
- Righe $1..N$: riga $i$, un intero, numero di mucca $i$ alla fine modulo $98,765,431$.
Esempi
Input 1
3 4 1 0 4
Output 1
26 25 29
Nota
Tre mucche, iniziali $1$, $0$, $4$, quattro ripetizioni.
Tabella dei numeri per turno:
| Turno | Mucca $1$ | Mucca $2$ | Mucca $3$ |
|---|---|---|---|
| $0$ | $1$ | $0$ | $4$ |
| $1$ | $4$ | $5$ | $1$ |
| $2$ | $6$ | $5$ | $9$ |
| $3$ | $14$ | $15$ | $11$ |
| $4$ | $26$ | $25$ | $29$ |
Ringraziamenti: Neal Wu, 2007