Obtained a pilot's license for an airplane (?)—no worries about supplies now. XXXX-XX-XX

Obtained a pilot's license for a jet (??)—now I can fly even faster. XXXX-XX-XX

Obtained a pilot's license for an attack aircraft (???)—(doesn't exist). XXXX-XX-XX

If you use lead plates for the interlayer, the fuselage will get heavy, you know. XXXX-XX-XX

Sachi's special delivery, precisely dropped at the target location.

Another peaceful day of nuclear deterrence.

Amane is performing maintenance on the jet and refueling it. This jet was specially crafted by a certain princess (?????), and its engine has three operating states:

1. Original: A low-power, high-efficiency state used for level flight at high altitudes or stealth flight.
2. Extended: A specially modified state to maximize energy efficiency during a dive.
3. Enhanced: A state used after a dive attack to generate extreme torque to gain altitude.

During an attack, the jet follows the workflow: "Original → Extended → Enhanced → Original".

The fuel efficiency varies across different operating states. Amane is currently adjusting the fuel loading sequence, and your task is to:

• Calculate the maximum total energy the fuel can produce.

Why you? Peace or nuclear deterrence—pick one.

The initial fuel sequence is empty. Each operation adds $x_i$ units of a specific type of fuel to the $p_i$-th position in the sequence.

The energy produced per unit of this fuel in the three operating states is $a_i, b_i, c_i$, respectively.

• The insertion position $p_i$ means that after the addition, there are $p_i$ units of original fuel before the first unit of the newly added fuel.
• All $x_i$ units of fuel are placed sequentially, and the fuel that was originally at position $p_i$ (if any) is shifted backward.

For a given fuel sequence, the maximum total energy it can produce is:

• The maximum sum of energy produced by dividing the sequence into four segments: "Original → Extended → Enhanced → Original" (each segment can be empty), where each segment generates energy according to its corresponding operating state.

For each addition operation, you need to output the increase in the maximum total energy resulting from that operation.

If you do not have an intuitive grasp of this calculation method, you can check the example explanation.

Input

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

The next $n$ lines each contain 5 integers $p_i, a_i, b_i, c_i, x_i$, separated by spaces, with the following meanings:

• $p_i$: The insertion position.
• $a_i, b_i, c_i$: The energy produced per unit of fuel in the Original, Extended, and Enhanced states, respectively.
• $x_i$: The quantity of fuel added.

Output

Output $n$ lines, each containing an integer representing the increase in the maximum total energy after that operation.

Examples

Input 1

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

Output 1

92
75
396
319
432

Note 1

After the first operation, the fuel sequence is [1 1]. The maximum energy configuration is [En1 En1], totaling $46 + 46 = 92$.

After the second operation, the fuel sequence is [1 2 2 2 1]. The maximum energy configuration is [Or1 Or2 Or2 Or2 En1], totaling $25 + 32 + 32 + 32 + 46 = 167$, an increase of $167 - 92 = 75$.

After the third operation, the fuel sequence is [1 2 2 3 3 3 3 2 1]. The maximum energy configuration is [Or1 Or2 Or2 Or3 Or3 Or3 Or3 Or2 En1], an increase of $99 \times 4 = 396$.

After the fourth operation, the fuel sequence is [1 2 4 4 4 4 4 2 3 3 3 2 1]. The maximum energy configuration 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 2 1 5 5 5 5 5 5]. The maximum energy configuration is [Or1 Or2 Ex4 Ex4 Ex4 Ex4 Ex4 Or2 Or3 Or3 Or3 Or3 Or2 Or1 Or5 Or5 Or5 Or5 Or5 Or5].

Subtasks

For $20\%$ of the data, $n \leq 1\,000$.

For $50\%$ of the data, $n \leq 10^4$.

For $100\%$ of the data: $1 \le n \le 10^5$, $1 \le a_i, b_i, c_i \le 10^4$, $1 \le x_i \le 10^9$. The last $50\%$ of the data contains a certain gradient.

It is guaranteed that at the time of insertion, there are at least $p_i$ units of fuel in the sequence.