405686: GYM102035 J Negative effect

Abu tahun has an array $$$a$$$ of $$$n$$$ positive integers, and a negative integer $$$m$$$.

Abu Tahun defines the beauty of the array as the maximum summation of a sub-array in that array.

A sub-array of an array is a sequence of consecutive integers in the array.

For example :

The beauty of array $$$\{1 , -5 , 7\}$$$ equals to $$$7$$$.

And the beauty of array $$$\{6 , -5 , 7\}$$$ equals to $$$8$$$.

in the second example we have the sub-arrays :

$$$\{6\}$$$ sum = 6, $$$\{-5\}$$$ sum = -5, $$$\{7\}$$$ sum = 7, $$$\{6,-5\}$$$ sum = 1, $$$\{-5,7\}$$$ sum = 2, $$$\{6,-5,7\}$$$ sum = 8.

You should tell Abu Tahun, for every index if he replaced the number in that index with $$$m$$$, what is the beauty of the resulting array.

First line of input contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n \leq 10^{5})$$$ $$$(-10^{9} \leq m < 0)$$$

The second line will contain $$$n$$$ integers, the $$$i_{th}$$$ one is $$$a_i$$$, which is the $$$i_{th}$$$ element in the array, $$$(1 \leq a_i \leq 10^{9})$$$.

You should print $$$n$$$ integers, the $$$i_{th}$$$ one should be the beauty of the given array after replacing the $$$i_{th}$$$ integer with $$$m$$$.

4 -3
1 2 3 4

9 7 4 6

In the first sample

after replacing the first index the array will become :

$$$\{-3,2,3,4\}$$$

the beauty equals to 9.

after replacing the second index the array will become :

$$$\{1,-3,3,4\}$$$

the beauty equals to 7.

after replacing the third index the array will become :

$$$\{1,2,-3,4\}$$$

the beauty equals to 4.

after replacing the fourth index the array will become :

$$$\{1,2,3,-3\}$$$

the beauty equals to 6.