2048 年, 第三十届 CSP 认证的考场上, 作为选手的小明打开了第一题。这个题的样例有 $n$ 组数据, 数据从 $1 \sim n$ 编号, $i$ 号数据的规模为 $a_{i}$ 。
小明对该题设计出了一个暴力程序, 对于一组规模为 $u$ 的数据, 该程序的运行时间为 $u^{2}$ 。然而这个程 序运行完一组规模为 $u$ 的数据之后, 它将在任何一组规模小于 $u$ 的数据上运行错误。样例中的 $a_{i}$ 不一 定递增, 但小明又想在不修改程序的情况下正确运行样例, 于是小明决定使用一种非常原始的解决方 案: 将所有数据划分成若干个数据段, 段内数据编号连续, 接着将同一段内的数据合并成新数据, 其 规模等于段内原数据的规模之和, 小明将让新数据的规模能够递增。
也就是说, 小明需要找到一些分界点 $1 \leq k_{1}<k_{2}<\cdots<k_{p}<n$, 使得$\sum_{i=1}^{k_{1}} a_{i} \leq \sum_{i=k_{1}+1}^{k_{2}} a_{i} \leq \cdots \leq \sum_{i=k_{p}+1}^{n} a_{i}$注意 $p$ 可以为 0 且此时 $k_{0}=0$, 也就是小明可以将所有数据合并在一起运行。
小明希望他的程序在正确运行样例情况下, 运行时间也能尽量小, 也就是最小化$\left(\sum_{i=1}^{k_{1}} a_{i}\right)^{2}+\left(\sum_{i=k_{1}+1}^{k_{2}} a_{i}\right)^{2}+\cdots+\left(\sum_{i=k_{p}+1}^{n} a_{i}\right)^{2}$小明觉得这个问题非常有趣, 并向你请教：给定 $n$ 和 $a_{i}$, 请你求出最优划分方案下, 小明的程序的最 小运行时间。

由于本题的数据范围较大, 部分测试点的 $a_{i}$ 将在程序内生成。
第一行两个整数 $n$, type 。 $n$ 的意义见题目描述, type 表示输入方式。
1.若 type $=0$, 则该测试点的 $a_{i}$ 直接给出。输入文件接下来：第二行 $n$ 个以空格分隔的整数 $a_{i}$, 表示每组数据的规模。
2.若 type $=1$, 则该测试点的 $a_{i}$ 将特殊生成, 生成方式见后文。输入文件接下来：第二行六个以空 格分隔的整数 $x, y, z, b_{1}, b_{2}, m$ 。接下来 $m$ 行中, 第 $i(1 \leq i \leq m)$ 行包含三个以空格分隔的正整 数 $p_{i}, l_{i}, r_{i}$ 。
对于 type $=1$ 的 23 25 号测试点, $a_{i}$ 的生成方式如下:
给定整数 $x, y, z, b_{1}, b_{2}, m$, 以及 $m$ 个三元组 $\left(p_{i}, l_{i}, r_{i}\right)$ 。
保证 $n \geq 2$ 。若 $n>2$, 则 $\forall 3 \leq i \leq n, b_{i}=\left(x \times b_{i-1}+y \times b_{i-2}+z\right) \bmod 2^{30}$ 。
对于所有 $1 \leq j \leq m$, 若下标值 $i(1 \leq i \leq n)$ 满足 $p_{j-1}<i \leq p_{j}$, 则有$a_{i}=\left(b_{i} \bmod \left(r_{j}-l_{j}+1\right)\right)+l_{j}$上述数据生成方式仅是为了减少输入量大小, 标准算法不依赖于该生成方式。

输出一行一个整数，表示答案。

[样例 1 解释]
最优的划分方案为 $\{5,1\},\{7\},\{9\},\{9\}$ 。由 $5+1 \leq 7 \leq 9 \leq 9$ 知该方案合法。 答案为 $(5+1)^{2}+7^{2}+9^{2}+9^{2}=247$ 。
虽然划分方案 $\{5\},\{1\},\{7\},\{9\},\{9\}$ 对应的运行时间比 247 小, 但它不是一组合法方案, 因为 $5>1$ 。
虽然划分方案 $\{5\},\{1,7\},\{9\},\{9\}$ 合法, 但该方案对应的运行时间为 251 , 比 247 大。
[样例 2 解释]
最优的划分方案为 $\{5\},\{6\},\{7\},\{7\},\{4,6,2\},\{13\},\{19,9\}$ 。
[数据范围]

对于 type $=0$ 的所有测试点,保证最后输出的答案 $\leq 4 \times 10^{18}$
所有测试点满足: type $\in\{0,1\}, 2 \leq n \leq 4 \times 10^{7}, 1 \leq a_{i} \leq 10^{9}, 1 \leq m \leq 10^{5}, 1 \leq l_{i} \leq$ $r_{i} \leq 10^{9}, 0 \leq x, y, z, b_{1}, b_{2}<2^{30}$ 。