题目描述

$\red{2048}$年，第三十届 CSP认证的考场上，作为选手的小明打开了第一题。这个题的样例有 $\red{n}$ 组数据，数据从 $\red{1 \sim n}$ 编号，$\red{i}$ 号数据的规模为 $\red{a_i}$。

小明对该题设计出了一个暴力程序，对于一组规模为 $\red{u}$ 的数据，该程序的运行时间为 $\red{u^2}$。然而这个程序运行完一组规模为 $\red{u}$ 的数据之后，它将在任何一组规模小于 $\red{u}$ 的数据上运行错误。样例中的 $\red{a_i}$ 不一定递增，但小明又想在不修改程序的情况下正确运行样例，于是小明决定使用一种非常原始的解决方案：将所有数据划分成若干个数据段，段内数据编号连续，接着将同一段内的数据合并成新数据，其规模等于段内原数据的规模之和，小明将让新数据的规模能够递增。

也就是说，小明需要找到一些分界点 $\red{1 \le k_1 < k_2 < \cdots < k_p < n}$，使得：

$\red{\sum_{i=1}^{k_1} a_i\le \sum_{i=k_1+1}^{k_2} a_i \le \dots \le \sum_{i=k_p+1}^n a_i}$

注意 $\red{p}$ 可以为 $\red{0}$ 且此时 $\red{k_0 = 0}$，也就是小明可以将所有数据合并在一起运行。

小明希望他的程序在正确运行样例情况下，运行时间也能尽量小，也就是最小化

$\red{\left(\sum_{i=1}^{k_1} a_i \right)^2+\left(\sum_{i=k_1}^{k_2} a_i \right)^2+\cdots +\left(\sum_{i=k_p+1}^n a_i \right)^2}$

小明觉得这个问题非常有趣，并向你请教：给定 $\red{n}$ 和 $\red{a_i}$，请你求出最优划分方案下，小明的程序的最小运行时间。

输入格式

由于本题的数据范围较大，部分测试点的 $\red{a_i}$ 将在程序内生成。

第一行两个整数 $\red{n, \text{type}}$。$\red{n}$ 的意义见题目描述，$\red{\text{type}}$ 表示输入方式。

1. 若 $\red{\text{type} = 0}$，则该测试点的 $\red{a_i}$ 直接给出。输入文件接下来：第二行 $\red{n}$ 个以空格分隔的整数 $\red{a_i}$，表示每组数据的规模。
2. 若 $\red{\text{type} = 1}$，则该测试点的 $\red{a_i}$ 将特殊生成，生成方式见后文。输入文件接下来：第二行六个以空格分隔的整数 $\red{x, y, z, b_1, b_2, m}$。接下来 $\red{m}$ 行中，第 $\red{i（1 \le i \le m）}$行包含三个以空格分隔的正整数 $\red{p_i, l_i, r_i}$。

对于 $\red{\text{type} = 1}$ 的 $\red{23 \sim 25}$ 号测试点，$\red{a_i}$ 的生成方式如下：

• 给定整数 $\red{x, y, z, b_1, b_2, m}$，以及 $\red{m}$ 个三元组 $\red{(p_i, l_i, r_i)}$。
• 保证 $\red{n \ge 2}$。若 $\red{n > 2}$，则 $\red{\forall 3\le i\le n}$，$\red{b_i = (x \times b_{i−1} + y \times b_{i−2} + z) \bmod 2^{30}}$。
• 保证 $\red{1 \le p_i \le n}$，$\red{p_m = n}$。令 $\red{p_0 = 0}$，则 $\red{p_i}$ 还满足 $\red{\forall 0 \le i < m}$ 有 $\red{p_i < p_{i+1}}$。
• 对于所有 $\red{1 \le j \le m}$，若下标值 $\red{i（1 \le i \le n）}$满足 $\red{p_{j−1} < i \le p_j}$，则有

$\red{a_i=\left( b_i \bmod (r_j-l_j+1) \right) +l_j}$

上述数据生成方式仅是为了减少输入量大小，标准算法不依赖于该生成方式。

输出格式

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

样例

输入样例 1

5 0
5 1 7 9 9

输出样例 1

247

样例说明 1

最优的划分方案为 $\red{\{5,1\},\{7\},\{9\},\{9\}}$。由 $\red{5 + 1 \le 7 \le 9 \le 9}$ 知该方案合法。

答案为 $\red{(5 + 1)^2 + 7^2 + 9^2 + 9^2 = 247}$。

虽然划分方案 $\red{\{5\},\{1\},\{7\},\{9\},\{9\}}$ 对应的运行时间比 $\red{247}$ 小，但它不是一组合法方案，因为 $\red{5 > 1}$。

虽然划分方案 $\red{\{5\},\{1,7\},\{9\},\{9\}}$ 合法，但该方案对应的运行时间为 $\red{251}$，比 $\red{247}$ 大。

输入样例 2

10 0
5 6 7 7 4 6 2 13 19 9

输出样例 2

1256

样例说明 2

最优的划分方案为 $\red{\{5\},\{6\},\{7\},\{7\},\{4,6,2\},\{13\},\{19,9\}}$。

输入样例 3

10000000 1
123 456 789 12345 6789 3
2000000 123456789 987654321
7000000 234567891 876543219
10000000 456789123 567891234

输出样例 3

4972194419293431240859891640

提示

测试点编号	$\red{n\le}$	$\red{a_i\le}$	$\red{\text{type}=}$
$\red{1\sim 3}$	$\red{10}$		$\red{0}$
$\red{4\sim 6}$	$\red{50}$	$\red{10^3}$
$\red{7\sim 9}$	$\red{400}$	$\red{10^4}$
$\red{10\sim 16}$	$\red{5\times 10^3}$	$\red{10^5}$
$\red{17\sim 22}$	$\red{5\times 10^5}$	$\red{10^6}$
$\red{23\sim 25}$	$\red{4\times 10^7}$	$\red{10^9}$	$\red{1}$

对于 $\red{\text{type} = 0}$ 的测试点，保证答案不超过 $\red{4\times 10^{18}}$。

所有测试点满足：$\red{\text{type} \in \{0, 1\} , 2 \le n \le 4 \times 10^7 , 1 \le a_i \le 10^9 , 1 \le m \le 10^5 ,1 \le l_i \le r_i \le 10^9 , 0 \le x, y, z, b_1, b_2 < 2^{30}}$。