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 <= n <= 10^5)$ $(-10^9 <= m < 0)$
The second line will contain $n$ integers, the $i_{t h}$ one is $a_i$, which is the $i_{t h}$ element in the array, $(1 <= a_i <= 10^9)$.
You should print $n$ integers, the $i_{t h}$ one should be the beauty of the given array after replacing the $i_{t h}$ integer with $m$.
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.
## Input
First line of input contains two integers $n$ and $m$ $(1 <= n <= 10^5)$ $(-10^9 <= m < 0)$The second line will contain $n$ integers, the $i_{t h}$ one is $a_i$, which is the $i_{t h}$ element in the array, $(1 <= a_i <= 10^9)$.
## Output
You should print $n$ integers, the $i_(t h)$ one should be the beauty of the given array after replacing the $i_(t h)$ integer with $m$.
[samples]
## Note
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.
**Definitions**
Let $ n \in \mathbb{Z}^+ $, $ m \in \mathbb{Z}^- $, and $ A = (a_1, a_2, \dots, a_n) $ with $ a_i \in \mathbb{Z}^+ $.
For each $ i \in \{1, \dots, n\} $, define the modified array $ A^{(i)} = (a_1, \dots, a_{i-1}, m, a_{i+1}, \dots, a_n) $.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ -10^9 \leq m < 0 $
3. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
**Objective**
For each $ i \in \{1, \dots, n\} $, compute:
$$
\text{beauty}(A^{(i)}) = \max_{1 \leq l \leq r \leq n} \sum_{j=l}^{r} A^{(i)}_j
$$
That is, the maximum subarray sum of $ A^{(i)} $.