$N$ krów $(1 \le N \le 50,000)$, wygodnie numerowanych $1..N$, uczy się szyfrowania. Po przykładach tworzą własne! Niedoświadczone, mają prosty algorytm:
Krowa $i$ otrzymuje początek $C_i$ $(0 \le C_i < 90,000,000)$, wszystkie wykonują równolegle:
- Najpierw każda sumuje liczby pozostałych $N-1$ krów.
- Gdy wszystkie skończą, każda zastępuje swoją liczbę obliczoną sumą. Unikają wielkich liczb, trzymając reszty modulo $98,765,431$.
W listopadzie powiedziały łosiowi Canmuu, zachwyconemu.
W mglistą Wigilię Canmuu powiedział:
„Za łatwo złamać! Powtarzajcie $T$ razy $(1 \le T \le 1,414,213,562)$”.
Sfrustrowane tyloma powtórzeniami nudnego algorytmu, po godzinach sporów z Canmuu uzgodniły: ty obliczysz liczby po szyfrowaniu!
*Pierwsze 10 zgłoszeń otrzyma dodatkowe informacje zwrotne.
Wejście
Czytaj standardowe wejście.
- Wiersz 1: całkowite $N$, $T$ ze spacją.
- Wiersze $2..N+1$: wiersz $i+1$ zawiera całkowite $C_i$.
Wyjście
Pisz standardowe wyjście.
- Wiersze $1..N$: wiersz $i$ zawiera jedną całkowitą, liczbę krowy $i$ na końcu modulo $98,765,431$.
Przykład
Wejście 1
3 4 1 0 4
Wyjście 1
26 25 29
Uwagi
Trzy krowy, początki $1$, $0$, $4$, cztery powtórzenia.
Tabela liczb krów w każdej rundzie:
| Runda | Krowa $1$ | Krowa $2$ | Krowa $3$ |
|---|---|---|---|
| $0$ | $1$ | $0$ | $4$ |
| $1$ | $4$ | $5$ | $1$ |
| $2$ | $6$ | $5$ | $9$ |
| $3$ | $14$ | $15$ | $11$ |
| $4$ | $26$ | $25$ | $29$ |
Podziękowania: Neal Wu, 2007