$N$ vacas $(1 \le N \le 50,000)$ numeradas por comodidad $1..N$ aprenden cifrado. Estudiaron ejemplos y crean el suyo. Sin mucha experiencia, su algoritmo es simple:
Cada vaca $i$ recibe valor inicial $C_i$ $(0 \le C_i < 90,000,000)$; todas en paralelo hacen:
- Primero cada una suma números de las otras $N-1$ vacas.
- Cuando todas terminan, reemplazan su propio número por su suma calculada. Evitan números grandes guardando el resto módulo $98,765,431$.
En noviembre lo contaron al alce Canmuu, impresionado.
Una Nochebuena de niebla, Canmuu dijo:
«¡Muy fácil de romper! Repítanlo $T$ veces $(1 \le T \le 1,414,213,562)$».
Frustradas por tantas repeticiones aburridas, tras horas discutiendo con Canmuu acordaron: ¡tú calculas los números tras el cifrado!
*Las primeras 10 entregas recibirán información adicional.
Entrada
Lee la entrada estándar.
- Línea 1: enteros $N$, $T$ separados por espacio.
- Líneas $2..N+1$: línea $i+1$, un entero $C_i$.
Salida
Escribe en salida estándar.
- Líneas $1..N$: línea $i$, un entero, número de vaca $i$ al terminar, módulo $98,765,431$.
Ejemplos
Entrada 1
3 4 1 0 4
Salida 1
26 25 29
Nota
Tres vacas con iniciales $1$, $0$, $4$, cuatro repeticiones.
Tabla de números de las vacas en cada ronda:
| Ronda | 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