Las ~N (1 \leq N \leq 50,000)~ vacas, convenientemente numeradas ~1..N~, están tratando de aprender algunos algoritmos de encriptamiento. ¡Después de estudiar unos cuantos ejemplos, ellas han decidido hacer uno propio de ellas! Sin embargo, ellas no tienen mucha experiencia con esto, de tal manera que su algoritmo es muy simple:

A cada vaca i se le da un número inicial ~C_i (0 \leq C_i < 90,000,000)~,y entonces todas las vacas ejecutan el siguiente proceso en paralelo:

• Primero, cada vaca encuentra la suma de los números de las otras ~N-1~ vacas.
• Después que todas las vacas han terminado, cada vaca reemplaza su número con la suma que ella ha calculado. Para evitar números muy grandes, las vacas guardan sus números modulo ~98,765,431~.

Ellas le contaron el algoritmo a Canmmu, el reno, en Noviembre; él se impresionó bastante.

Luego en una víspera nublada de Navidad, Canmmuu apareció diciendo: "¡Su algoritmo es muy fácil de romper! En vez de hacerlo una vez, ustedes deberían repetirlo ~T (1 \leq T \leq 1,414,213,562)~ veces."

Obviamente, las vacas estaban frustradas teniendo que ejecutar tantas repeticiones del mismo algoritmo aburrido, por lo tanto después de varias horas de discusión, Canmuu y las vacas llegaron a un acuerdo: ¡Usted debe de calcular los números que quedan después que el encriptamiento es ejecutado!

Entrada

• Línea 1: Dos números separados por un espacio: ~N~ y ~T~
• Líneas 2..N+1: La línea i+1 contiene un solo entero: ~C_i~

Ejemplo de Entrada

3 4
1
0
4

Detalles de la Entrada

Tres vacas, con números iniciales 1, 0, y 4; cuatro repeticiones del algoritmo de encriptamiento.

Salida

Líneas 1..N: La línea i contiene un solo entero representando el número de la vaca i (modulo ~98,765,431~) al final del encriptamiento.

Ejemplo de Salida

26
25
29

Detalles de la Salida

La tabla siguiente muestra los números de las vacas cada vez que se aplica el algoritmo:

    Números de las vacas
Turno   Vaca1  Vaca2  Vaca3
 0        1      0      4
 1        4      5      1
 2        6      5      9
 3       14     15     11
 4       26     25     29