Description

The initial fuel sequence is empty. Each operation inserts $x _ i$ units of the same type of fuel at position $p _ i$ in the sequence. For this fuel, each unit can produce energy $a _ i, b _ i, c _ i$ in the three operating states, respectively.

The position $p _ i$ means that, after insertion, there are $p _ i$ units of the original fuel in front of the first inserted unit.

All $x _ i$ units are placed consecutively. Then the fuel that originally started at position $p _ i$ (if any) is shifted backward in order.

For a fixed fuel sequence, its maximum total energy is defined as follows: split the sequence into four consecutive segments in the order “Original → Extended → Enhanced → Original” (each segment may be empty). The total energy is the sum, over all units, of the energy corresponding to the state of the segment they belong to. Take the maximum value over all such splits.

For each insertion operation, output by how much the maximum total energy increases due to this operation.

If this calculation is not intuitive, see the sample explanation.

Input Format

The first line contains an integer $n$, the number of operations.

Each of the next $n$ lines contains $5$ integers $p _ i, a _ i, b _ i, c _ i, x _ i$, separated by spaces, indicating that $x _ i$ units of the same fuel are inserted at position $p _ i$ in the sequence.

For this fuel, each unit produces $a _ i, b _ i, c _ i$ energy in the Original, Extended, and Enhanced states, respectively.

Output Format

Output $n$ lines. Each line contains a single integer, the increase in the maximum total energy after that operation.

5
0 25 37 46 2
1 32 14 16 3
3 99 77 88 4
2 43 68 57 5
14 72 36 18 6

92
75
396
319
432

Hint

After the first operation, the fuel sequence is “[1 1]”. The way to achieve maximum energy is “[En1 En1]”, totaling $46+46=92$.

After the second operation, the fuel sequence is “[1 2 2 2 1]”. The way to achieve maximum energy is “[Or1 Or2 Or2 Or2 En1]”, totaling $25+32+32+32+46=167$, increased by $167-92=75$.

After the third operation, the fuel sequence is “[1 2 2 3 3 3 3 2 1]”. The way to achieve maximum energy is “[Or1 Or2 Or2 Or3 Or3 Or3 Or3 Or2 En1]”, increased by $99\times 4=396$.

After the fourth operation, the fuel sequence is “[1 2 4 4 4 4 4 2 3 3 3 3 2 1]”. The way to achieve maximum energy is “[Or1 Or2 Ex4 Ex4 Ex4 Ex4 Ex4 Or2 Or3 Or3 Or3 Or3 Or2 Or1]”.

After the fifth operation, the fuel sequence is “[1 2 4 4 4 4 4 2 3 3 3 3 2 1 5 5 5 5 5 5]”. The way to achieve maximum energy is “[Or1 Or2 Ex4 Ex4 Ex4 Ex4 Ex4 Or2 Or3 Or3 Or3 Or3 Or2 Or1 Or5 Or5 Or5 Or5 Or5 Or5]”.

For $100\%$ of the testdata, $1 \leq n \leq 10^5$, $1 \leq a_i, b_i, c_i \leq 10^4$, $1 \leq x_i \leq 10^9$.

For $100\%$ of the testdata, it is guaranteed that at the time of insertion there are at least $p _ i$ units of fuel already in the sequence.

The remaining $50\%$ of the testdata has graded difficulty.

Translated by ChatGPT 5