Maximizing Energy Production with Fuel Insertions

We start with an empty fuel sequence. There will be several operations. In each operation, you insert x units of fuel at position p (i.e. after the first p fuel units, if any) into the current sequence. All x fuel units inserted in the same operation are identical – each unit has three associated energy parameters: \(a, b, c\). Each fuel unit, when operating in one of three states, produces energy \(a\), \(b\) or \(c\) per unit respectively.

The final energy production of a determined fuel sequence is computed as follows. Partition the sequence (in order) into four contiguous segments (each segment may be empty) with states:

• First segment: Normal state (energy per unit \(a\)).
• Second segment: Late state (energy per unit \(b\)).
• Third segment: Enhanced state (energy per unit \(c\)).
• Fourth segment: Normal state (energy per unit \(a\)).

The maximum total energy is the maximum possible sum of energies over all such partitions. Formally, if the fuel sequence has length \(N\), and if we choose indices \(0\le i\le j\le k\le N\) to partition the sequence into segments:

[ E = \sum_{t=1}^{N}a_t + \max_{0\le i\le j\le k\le N} \Bigl{\bigl[(PB(j)-PB(i)) + (PC(k)-PC(j)) - (PA(k)-PA(i)\bigr]\Bigr}, ]

where for \(1\le t\le N\), each fuel unit \(t\) has parameters \(a_t,b_t,c_t\) and

[ PA(x)=\sum_{t=1}^{x} a_t,\quad PB(x)=\sum_{t=1}^{x} b_t,\quad PC(x)=\sum_{t=1}^{x} c_t \quad (PA(0)=PB(0)=PC(0)=0). ]

After some algebra the maximum energy can be computed in \(O(N)\) time per query as follows. Define arrays (for \(0\le i\le N\)):

[ X[i]=PA(i)-PB(i),\quad Y[i]=PB(i)-PC(i),\quad Z[i]=PC(i)-PA(i). ]

Then let

[ L[j]=\max_{0\le i\le j} X[i], \quad R[j]=\max_{j\le k\le N} Z[k]. ]

Thus the maximum additional energy above \(PA(N)\) is

[ \max_{0\le j\le N} \Bigl(L[j]+Y[j]+R[j]\Bigr), ]

and the total maximum energy is

[ PA(N)+\max_{0\le j\le N} \Bigl(L[j]+Y[j]+R[j]\Bigr). ]

Your task is, for each insertion operation, to compute the increase in the maximum total energy caused by that operation. That is, if before the operation the maximum energy was \(E_{old}\) and after the operation it is \(E_{new}\), output \(E_{new}-E_{old}\). Note that the sequence is built up gradually over operations.

For example, if an operation inserts 1 unit of fuel with parameters \((a,b,c)=(1,2,3)\) at position 0 into an empty sequence then the maximum total energy becomes 3. In a later operation, fuel is inserted into the sequence and you must output the incremental increase.

inputFormat

The first line contains a single integer \(q\) (the number of operations). Each of the following \(q\) lines contains five integers:

• \(p\): the number of fuel units before the insertion position.
• \(x\): number of fuel units to insert.
• \(a, b, c\): the energy parameters for each inserted unit in the three states.

It is guaranteed that \(0\le p\le \) (current length of the sequence) for each operation.

outputFormat

For each operation, output a single line with one integer – the increase in the maximum total energy after that operation.

sample

1
0 1 1 2 3

3

</p>