Description

初始燃料序列为空。每次操作会向序列中的 $p _ i$ 位置添加 $x _ i$ 单位的同种燃料，该燃料每一单位在三种工作状态下能产生的能量分别为 $a _ i, b _ i, c _ i$。

添加的位置 $p _ i$ 是指，在添加后，加入的第一个单位燃料前面有 $p _ i$ 个单位的原燃料。

全部的 $x _ i$ 单位燃料依次放置，然后原来在 $p _ i$ 位置的燃料（如果有的话）依次向后排列。

对于一个确定的燃料序列，其能产生的最大总能量为：将序列依次分成"通常-后期-增强-通常"四段（每段可以为空），每一段在对应工作状态下产生的能量之和的最大值。

对于每次添加操作，你需要给出该次操作使得最大总能量增加了多少。

如果对于这种计算方式没有直观的感受，可以查看样例说明。

Input Format

第一行一个数 $n$，表示操作个数。

接下来 $n$ 行，每行 $5$ 个数 $p _ i, a _ i, b _ i, c _ i, x _ i$，空格分隔，表示向序列中的 $p _ i$ 位置添加 $x _ i$ 单位的同种燃料

这种燃料每单位在通常、后期、增强工作状态下产生的能量分别为 $a _ i, b _ i, c _ i$。

Output Format

$n$ 行，每行一个数，表示该次操作后能量序列所能产生的最大总能量增加了多少。

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

第一次操作后，燃料序列为 [1 1]，最大能量发生方式为 [En1 En1]，共 $46+46=92$。

第二次操作后，燃料序列为 [1 2 2 2 1]，最大能量发生方式为 [Or1 Or2 Or2 Or2 En1]，共 $25+32+32+32+46=167$，增加了 $167-92=75$。

第三次操作后，燃料序列为 [1 2 2 3 3 3 3 2 1]，最大能量发生方式为 [Or1 Or2 Or2 Or3 Or3 Or3 Or3 Or2 En1]，增加了 $99\times 4=396$。

第四次操作后，燃料序列为 [1 2 4 4 4 4 4 2 3 3 3 3 2 1]，最大能量发生方式为 [Or1 Or2 Ex4 Ex4 Ex4 Ex4 Ex4 Or2 Or3 Or3 Or3 Or3 Or2 Or1]。

第五次操作后，燃料序列为 [1 2 4 4 4 4 4 2 3 3 3 3 2 1 5 5 5 5 5 5]，最大能量发生方式为 [Or1 Or2 Ex4 Ex4 Ex4 Ex4 Ex4 Or2 Or3 Or3 Or3 Or3 Or2 Or1 Or5 Or5 Or5 Or5 Or5 Or5]。

对于 $100\%$ 的数据，$1 \leq n \leq 10^5$, $1 \leq a_i, b_i, c_i \leq 10^4$， $1 \leq x_i \leq 10^9$。

对于 $100\%$ 的数据，保证插入时序列中至少已有 $p _ i$ 单位的燃料。

后 $50\%$ 数据有梯度。