Sweetest Candy

All submissions for this problem are available.
### Read problems statements in [Hindi](http://www.codechef.com/download/translated/COOK115/hindi/SUBMAXA.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/COOK115/mandarin/SUBMAXA.pdf), [Russian](http://www.codechef.com/download/translated/COOK115/russian/SUBMAXA.pdf), [Vietnamese](http://www.codechef.com/download/translated/COOK115/vietnamese/SUBMAXA.pdf), and [Bengali](http://www.codechef.com/download/translated/COOK115/bengali/SUBMAXA.pdf) as well. Chef wants to buy candy for his friend. He went to a store which sells candies from $N$ jars, arranged in a circle and numbered $1$ through $N$ in such a way that for each valid $i$, jars $i$ and $i+1$ are adjacent, and jars $1$ and $N$ are also adjacent. For each valid $i$, the candies in the $i$th jar have a sweetness $A_i$. Obviously, Chef wants to buy the sweetest candies. However, he gets attracted by a limitedtime offer in the store and wants to use it. The offer is as follows: Chef has to choose an integer $k$ ($1 \le k \le N$), then choose $k$ jars which are contiguous in the circle, and finally, he can buy the candies from these jars at a discounted price. For a fixed $k$, Chef chooses the $k$ contiguous jars uniformly randomly (among all possible sets of $k$ contiguous jars), but once he chooses them, he buys only candies with the largest sweetness among the chosen jars. As you may have guessed, Chef is confused about which value of $k$ to choose. For each valid $k$, let's denote the expected value of the sweetness of the candies he will buy if he chooses this value of $k$ by $S_k$. Then, let's denote $F_k = S_k \cdot N$; it can be proved that for each valid $k$, $F_k$ is an integer. Can you help Chef find the values of $F_1, F_2, \ldots, F_N$? ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains a single integer $N$.  The second line contains $N$ spaceseparated integers $A_1, A_2, \ldots, A_N$. ### Output For each test case, print a single line containing $N$ spaceseparated integers $F_1, F_2, \ldots, F_N$. ### Constraints  $1 \le T \le 10$  $1 \le N \le 10^6$  $1 \le A_i \le 10^9$ for each valid $i$  the sum of $N$ over all test cases does not exceed $10^6$ ### Example Input ``` 1 4 1 2 3 4 ``` ### Example Output ``` 10 13 15 16 ```Author:  teja349 
Editorial  https://discuss.codechef.com/problems/SUBMAXA 
Tags  akashbhalotia, cook115, differencearray, expectedvalue, medium, nextgreaterelement, prefixsum, rotation, rotationtrick, teja349 
Date Added:  8022020 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, CPP17, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 