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 C_{i} (0 ≤ C_{i} < 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 N1 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 spaceseparated integers: N and T.
 Lines 2..N+1: Line i+1 contains a single integer: C_{i}.
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 29Warning: large input/output data.
hide comments
infyy:
20180601 10:15:44
Getting WA in last test case even though I have used 98765431 

druh:
20171201 14:24:58
WA on 14 :( Help PLEASE!


fresh:
20160127 04:14:24
sorry for that


fresh:
20160126 14:49:21
there is something wrong with this problem


Mahmoud A Gawad:
20151011 18:27:30
1. Don't use scanf("%I64d",...) > It will give you WA in test 14


Harish Meena:
20151001 17:55:18
why is number 14 giving WA?? 

::
20150123 08:52:19
@kriti, how ans can be <0. all things are summation of positive integers only! 

Kriti Joshi:
20141219 05:39:53
@Doshi I think it is O(n+log(t)). WA at test case 8 may be due to not including if(ans<0)ans+=98765431 Last edit: 20141219 06:20:32 

gyosh:
20141017 07:46:07
If you are getting WA in test case 14, you probably typed 987654321 as the modulo. The correct number is 98765431 (without 2) 

Pratyush Kar:
20140719 19:50:01
nice question 
Added by:  Neal Wu 
Date:  20080528 
Time limit:  0.160s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO 
Resource:  USACO Chn 2007 