SUMSUMS - Summing Sums

The N (1 ≤ N ≤ 50,000) cows, conveniently numbered 1, 2, ..., N, are trying to learn some encryption algorithms. After studying a few examples, they have decided to make one of their own! However, they are not very experienced at this, so their algorithm is very simple:

Each cow i is given a starting number Ci (0 ≤ Ci < 90,000,000), and then all the cows perform the following process in parallel:

  • First, each cow finds the sum of the numbers of the other N-1 cows.
  • After all cows are finished, each cow replaces her number with the sum she computed. To avoid very large numbers, the cows will keep track of their numbers modulo 98,765,431.

They told Canmuu the moose about it in November; he was quite impressed. Then one foggy Christmas Eve, Canmuu came to say:

"Your algorithm is too easy to break! You should repeat it T (1 ≤ T ≤ 1,414,213,562) times instead."

Obviously, the cows were very frustrated with having to perform so many repetitions of the same boring algorithm, so after many hours of arguing, Canmuu and the cows reached a compromise: You are to calculate the numbers after the encryption is performed!

Input

  • Line 1: Two space-separated integers: N and T.
  • Lines 2..N+1: Line i+1 contains a single integer: Ci.

Output

  • Lines 1..N: Line i contains a single integer representing the number of cow i (modulo 98,765,431) at the end of the encryption.

Example

Input:
3 4
1
0
4

Output:
26
25
29

The following is a table of the cows' numbers for each turn:

          Cows' numbers
Turn    Cow1  Cow2  Cow3
 0        1     0     4
 1        4     5     1
 2        6     5     9
 3       14    15    11
 4       26    25    29
Warning: large input/output data.

Added by:Neal Wu
Date:2008-05-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO
Resource:USACO Chn 2007

hide comments
2014-01-19 13:55:13 Shreyans
Getting constantly TLE at running...(14)
What is best complexity?
2013-07-04 09:21:28 achiever202
i get wrong answer after runnig(14)... any hint...??
2013-04-03 16:59:28 NodaR M JarraR
after running 14 i am getting a wrong answer ,,,, what may be the problem :/ ??
2013-03-24 21:30:27 Divanshu
The MOD value is 98765431 and NOT 9876543(2)1 here! Caused me a WA. :(

Last edit: 2013-03-24 21:30:58
2013-03-20 08:14:05 Shubham Depp Bansal
Somebody please help.I am getting correct answer till 13(logic must be correct) but i dont know why its getting wrong in 14..Please tell me some exceptional test cases

Last edit: 2013-03-20 08:15:15
2013-01-05 21:46:33 Kyuubi Sage Mode
For the sample test case my answer comes out to be 126 125 129 please help

Sorry-Stupid Mistake

Last edit: 2013-01-06 15:27:20
2012-12-24 04:41:57 npsabari
think in-terms of simple matrices!
2012-01-03 16:28:58 Stefanot
matrix power
2011-12-21 11:51:40 Aditya Muttur
what sort of an algorithm can handle so many iterations?
2010-08-09 09:04:17 David Gómez
@Ishan My code gives 0 for that test case
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.