409608: GYM103643 K Cards
Description
Goma has asked Peach to play a little game. Goma has put $$$N$$$ ($$$1 \leq N \leq 2 \cdot 10^5$$$) face up cards in a circle labeled $$$1$$$ to $$$N$$$ clockwise where the $$$i$$$th card has the number $$$a_i$$$ on it ($$$1 \leq a_i \leq 10^9$$$). Goma simply tells Peach to pick a number $$$k$$$ from $$$1$$$ to $$$N$$$ inclusive, and to take a sum of the cards in the following fashion: To begin, flip the first card face down. Then go $$$k$$$ cards clockwise and if the card is face up, flip it face down and continue the process, otherwise stop. Then take the sum of all the face down cards. Peach is curious and would like to know what sum they would get for each $$$k$$$ from $$$1$$$ to $$$N$$$.
InputThe first line contains $$$N$$$.
The next line contains $$$N$$$ integers denoting $$$a_1, a_2,...,a_N$$$.
Test case 1 is the sample and will not be worth points.
Test case 2-4: $$$N \leq 1000$$$
Test cases 5-21: No further constraints
OutputOutput $$$N$$$ lines, where the $$$i$$$th line is the resulting sum when Goma chooses $$$k = i$$$.
ExampleInput5 1 2 3 4 5Output
15 15 15 15 1Note
If $$$k = 2$$$, and $$$N = 5$$$, Peach would flip the 1st card face down, then the 3rd, then the 5th, then the 2nd, then the 4th, then stop since the 1st card is already face down. Since all the cards are face down the sum we get is $$$1 + 2 + 3 + 4 + 5 = 15$$$.
$$$---------------------------------------------$$$
Problem Idea: Bossologist
Problem Preparation: Bossologist
Occurrences: Intermediate 8, Advanced 6