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.
