**Jacobsthal numbers** are analogous to fibonacci numbers

their series is **0 1 1 3 5 11 21 43 85…**

Now I came across an interesting problem where i found use of this not so well-known series

if u want to know more abt this series LINK

The problem is :

**PROBLEM STARTS HERE**

The problem setter for this contest is also setting up problems for IHPC (in Techkriti).

There, he encountered a new field of writing parallel code and a totally new thinking style to go about solving algorithmic problems by doing computations in parallel.

He created the following problem:

He takes N processors numbered 1, 2, …, N. Each processors is initially given a number Ci and then all of them perform the following process in parallel:

First, each processor finds the sum of the numbers of the other N-1 processors.

After all processors are finished, each processor replaces its number with the sum it computed. To avoid very large numbers, the processors will keep track of their numbers modulo 98,765,431.

To make it more tough, he sets the processors to repeat this algorithm T times.

After thinking a bit more on the problem, he realised that this can also be solved very efficiently using sequential code instead. So, he decided to check if the Algorithmic community of IITK, the teams practicing for IOPC can solve it or not?

Constraints

1 ≤ N ≤ 50,000

0 ≤ Ci < 90,000,000

1 ≤ T ≤ 109

Input

Each input file consists of a single test case. Line 1 contains two space-separated integers, N and T.

From Lines 2 … N+1, line i+1 contains a single integer Ci.

Output

N lines, where line i contains a single integer representing the number computed by processor i

(modulo 98,765,431) at the end of the T iterations of the algorithm.

Sample Input

3 4

1

0

4

Sample Output

26

25

29

**PROBLEM ENDS**

Now i tried it solving using an example and derived a formula (I’m sure it’s correct)

after **t** iterations the elements of the array will be : * jt(S) + (-1)^t(a)**

here jt -> 't’th jacobsthal number

a -> that particular element of array

S -> sum of all elements of array

Now that everything is set and i wrote code which produces jacobsthal numbers in linear time

that’s giving me TLE

so please help me to find jacobsthal numbers in O(logn) time ( just like fibonacci numbers )

Thank You