$N$ vaches $(1 \le N \le 50,000)$ numérotées commodément $1..N$ apprennent le chiffrement. Quelques exemples étudiés, elles créent le leur ! Peu expérimentées, leur algorithme est simple :
Chaque vache $i$ reçoit $C_i$ $(0 \le C_i < 90,000,000)$ au départ, puis toutes font en parallèle :
- D'abord chacune somme les nombres des $N-1$ autres.
- Quand toutes ont fini, chacune remplace son nombre par sa somme calculée. Pour éviter les grands nombres, elles gardent le reste modulo $98,765,431$.
En novembre, elles en parlent à l'élan Canmuu, impressionné.
Une veille de Noël brumeuse, Canmuu vient dire :
« Trop facile à casser ! Répétez plutôt $T$ fois $(1 \le T \le 1,414,213,562)$ ».
Les vaches sont frustrées de répéter tant ce même algorithme ennuyeux. Après des heures de dispute avec Canmuu, compromis : vous calculez les nombres après chiffrement !
*Les 10 premières soumissions recevront un retour supplémentaire.
Entrée
Lisez l'entrée standard.
- Ligne 1 : entiers $N$, $T$ séparés par espace.
- Lignes $2..N+1$ : ligne $i+1$, un entier $C_i$.
Sortie
Écrivez sur la sortie standard.
- Lignes $1..N$ : ligne $i$, un entier, nombre de la vache $i$ après chiffrement modulo $98,765,431$.
Exemples
Entrée 1
3 4 1 0 4
Sortie 1
26 25 29
Remarque
Trois vaches, valeurs initiales $1$, $0$, $4$, quatre répétitions.
Table des nombres des vaches à chaque tour :
| Tour | Vache $1$ | Vache $2$ | Vache $3$ |
|---|---|---|---|
| $0$ | $1$ | $0$ | $4$ |
| $1$ | $4$ | $5$ | $1$ |
| $2$ | $6$ | $5$ | $9$ |
| $3$ | $14$ | $15$ | $11$ |
| $4$ | $26$ | $25$ | $29$ |
Remerciements : Neal Wu, 2007