405439: GYM101962 K Rei do Cangaço

João has just bought a new game from the store: Lampião, o Rei do Cangaço. The main character of the game is Lampião, a known figure of Soteropolitan culture and probably the most famous cangaceiro of all time. There is a lot of controversy around the reputation of the cangaceiros, but João definitely must stick to their cause to beat this game.

In this game, João must control Lampião through a series of mini-games. There is one mini-game that caught João's attention: the treasure hunt. In this mini-game, there are $$$n$$$ houses in a row, numbered 1 to $$$n$$$ from left to right. Lampião is supposed to break into some of these houses. After breaking into a house, Lampião may earn or lose coins (some houses are guarded by jagunços, which are dangerous mercenaries crazy for money). More specifically, let $$$C$$$ be how many coins Lampião possesses before breaking into the $$$i$$$-th house. Lampião will have $$$C + a_i$$$ coins after breaking into it, where $$$a_i$$$ may actually be negative.

Lampião is initially standing in front of one of the houses. Also, he initially possesses $$$10^9$$$ coins. The game is played in turns. The turns are numbered starting from one. In the $$$i$$$-th turn, one of the two actions below can be taken:

1. Move Lampião $$$3i$$$ houses to the right while breaking into every one of them, except for the final one. For instance, if this is the first turn, there are 4 houses, Lampião is standing by house 1 and this action is taken, Lampião will move to house 4 while breaking into houses 1, 2 and 3;
2. Just move Lampião $$$3i$$$ houses to the right.

The game instantly ends when Lampião goes beyond the $$$n$$$-th house.

Your task is to compute, for every possible starting position, the maximum profit Lampião can achieve if João acts optimally. The profit is defined as the difference between the final amount of coins and the initial amount of coins. Notice that the optimal profit is never negative, since João can choose not to take action (1).

The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 50000$$$) – the number of houses in the mini-game.

The second line contains $$$n$$$ space-separated integers. The $$$i$$$-th of them is $$$a_i$$$ ($$$-300 \leq a_i \leq 300$$$).

Print $$$n$$$ lines. The $$$i$$$-th of them should contain a single integer – the maximum possible profit if Lampião starts from the $$$i$$$-th house.

5
1 2 3 4 -5

6
9
2
0
0

7
-3 -5 -7 -9 9 -2 -4

0
3
0
0
3
0
0

9
1 2 3 4 5 6 5 -7 2

21
20
18
15
16
6
0
0
2

4
1 -1 2 3

5
4
5
3