{"raw_statement":[{"iden":"statement","content":"Abu tahun has an array $a$ of $n$ positive integers, and a negative integer $m$.\n\nAbu Tahun defines the beauty of the array as the maximum summation of a sub-array in that array.\n\nA sub-array of an array is a sequence of consecutive integers in the array.\n\nFor example :\n\nThe beauty of array ${1, -5, 7}$ equals to $7$.\n\nAnd the beauty of array ${6, -5, 7}$ equals to $8$.\n\nin the second example we have the sub-arrays :\n\n${6}$ sum = 6, ${-5}$ sum = -5, ${7}$ sum = 7, ${6, -5}$ sum = 1, ${-5, 7}$ sum = 2, ${6, -5, 7}$ sum = 8.\n\nYou 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.\n\nFirst line of input contains two integers $n$ and $m$ $(1 <= n <= 10^5)$ $(-10^9 <= m < 0)$\n\nThe 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)$.\n\nYou 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$.\n\nIn the first sample \n\nafter replacing the first index the array will become : \n\n${-3, 2, 3, 4}$\n\nthe beauty equals to 9.\n\nafter replacing the second index the array will become : \n\n${1, -3, 3, 4}$\n\nthe beauty equals to 7.\n\nafter replacing the third index the array will become : \n\n${1, 2, -3, 4}$\n\nthe beauty equals to 4.\n\nafter replacing the fourth index the array will become : \n\n${1, 2, 3, -3}$\n\nthe beauty equals to 6.\n\n"},{"iden":"input","content":"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)$."},{"iden":"output","content":"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$."},{"iden":"note","content":"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."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ m \\in \\mathbb{Z}^- $, and $ A = (a_1, a_2, \\dots, a_n) $ with $ a_i \\in \\mathbb{Z}^+ $.  \nFor 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) $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ -10^9 \\leq m < 0 $  \n3. $ 1 \\leq a_i \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\} $  \n\n**Objective**  \nFor each $ i \\in \\{1, \\dots, n\\} $, compute:  \n$$\n\\text{beauty}(A^{(i)}) = \\max_{1 \\leq l \\leq r \\leq n} \\sum_{j=l}^{r} A^{(i)}_j\n$$  \nThat is, the maximum subarray sum of $ A^{(i)} $.","simple_statement":"You are given an array of n positive integers and a negative number m.  \nFor each position i, replace the i-th element with m, then find the maximum sum of any contiguous subarray (beauty) of the new array.  \nPrint the beauty for each replacement.","has_page_source":false}