$N$ Kühe $(1 \le N \le 50,000)$, bequem $1..N$ nummeriert, lernen Verschlüsselung. Nach Beispielen entwickeln sie eine eigene! Da sie unerfahren sind, ist ihr Algorithmus einfach:
Kuh $i$ bekommt Anfangswert $C_i$ $(0 \le C_i < 90,000,000)$, alle führen parallel aus:
- Zuerst summiert jede die Zahlen der anderen $N-1$ Kühe.
- Wenn alle fertig sind, ersetzt jede ihre Zahl durch ihre berechnete Summe. Gegen große Zahlen speichern sie Reste modulo $98,765,431$.
Im November erzählten sie Elch Canmuu, der beeindruckt war.
An einem nebligen Heiligabend sagte Canmuu:
„Zu leicht zu knacken! Wiederholt $T$ mal $(1 \le T \le 1,414,213,562)$.“
Frustriert über viele langweilige Wiederholungen, einigten sie sich nach stundenlangem Streit mit Canmuu: Du berechnest die Zahlen nach Verschlüsselung!
*Die ersten 10 Einreichungen erhalten zusätzliches Feedback.
Eingabe
Lies die Standardeingabe.
- Zeile 1: Ganzzahlen $N$, $T$ mit Leerzeichen.
- Zeilen $2..N+1$: Zeile $i+1$, eine Ganzzahl $C_i$.
Ausgabe
Schreibe auf Standardausgabe.
- Zeilen $1..N$: Zeile $i$, eine Ganzzahl, Zahl der Kuh $i$ am Ende modulo $98,765,431$.
Beispiele
Eingabe 1
3 4 1 0 4
Ausgabe 1
26 25 29
Hinweis
Drei Kühe, Anfangswerte $1$, $0$, $4$, vier Wiederholungen.
Tabelle der Zahlen je Runde:
| Runde | Kuh $1$ | Kuh $2$ | Kuh $3$ |
|---|---|---|---|
| $0$ | $1$ | $0$ | $4$ |
| $1$ | $4$ | $5$ | $1$ |
| $2$ | $6$ | $5$ | $9$ |
| $3$ | $14$ | $15$ | $11$ |
| $4$ | $26$ | $25$ | $29$ |
Danksagung: Neal Wu, 2007