Person in Charge

Attention

The data range of this problem is not exactly the same as the original problem.

Problem Description

In 2048, in the examination room of the 30th CSP Certification, Xiao Ming, a contestant, opened the first problem. This problem has $n$ groups of sample data, numbered from $1$ to $n$, and the scale of the $i$-th group of data is $a_i$.

Xiao Ming designed a brute-force program for this problem. For a group of data with scale $u$, the running time of the program is $u^2$. However, after the program runs a group of data with scale $u$, it will run incorrectly on any group of data with a scale smaller than $u$. The $a_i$ in the sample are not necessarily increasing, but Xiao Ming wants to run the sample correctly without modifying the program, so he decides to use a very primitive solution: divide all data into several consecutive data segments (the numbers of data in a segment are consecutive), then merge the data in the same segment into new data whose scale is equal to the sum of the scales of the original data in the segment, and Xiao Ming will make the scales of the new data non-decreasing.

That is to say, Xiao Ming needs to find some dividing points $1 \le k_1 \lt k_2 \lt \cdots \lt k_p \lt n$ such that:

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

Note that $p$ can be $0$ (in this case $k_0 = 0$), which means Xiao Ming can merge all data and run them together.

Xiao Ming hopes that under the condition that the program runs the sample correctly, the running time is as small as possible, that is, to minimize:

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

Xiao Ming thinks this problem is very interesting and asks you for help: given $n$ and $a_i$, please find the minimum running time of Xiao Ming's program under the optimal partitioning scheme.

Input Format

Due to the large data range of this problem, the $a_i$ of some test points will be generated within the program.

The first line contains two integers $n, type$. $n$ has the meaning described in the problem, and $type$ indicates the input method:

1. If $type = 0$, the $a_i$ of this test point are given directly. Next in the input file: the second line contains $n$ integers $a_i$ separated by spaces, representing the scale of each group of data.
2. If $type = 1$, the $a_i$ of this test point will be generated specially, and the generation method is described later. Next in the input file: the second line contains six integers $x, y, z, b_1, b_2, m$ separated by spaces. The next $m$ lines each contain three positive integers $p_i, l_i, r_i$ separated by spaces (the $i$-th line, $1 \le i \le m$).

For test points $23 \sim 25$ with $type = 1$, the generation method of $a_i$ is as follows:

Given integers $x, y, z, b_1, b_2, m$, and $m$ triples $(p_i, l_i, r_i)$.

It is guaranteed that $n \ge 2$. If $n \gt 2$, then $\forall 3 \le i \le n, b_i = (x \times b_{i−1} + y \times b_{i−2} + z) \mod 2^{30}$.

It is guaranteed that $1 \le p_i \le n$ and $p_m = n$. Let $p_0 = 0$, then $p_i$ also satisfies $\forall 0 \le i \lt m$, $p_i \lt p_{i+1}$.

For all $1 \le j \le m$, if the subscript $i (1 \le i \le n)$ satisfies $p_{j−1} \lt i \le p_j$, then:

$$a_i = \left(b_i \mod \left( r_j − l_j + 1 \right) \right) + l_j$$

The above data generation method is only to reduce the size of the input file, and the standard algorithm does not depend on this generation method.

Output Format

Output a single integer on one line, representing the answer.

Samples

5 0
5 1 7 9 9

247

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

1256

Sample 1 Explanation

The optimal partitioning scheme is $\{5,1\}, \{7\}, \{9\}, \{9\}$. It is a valid scheme because $5 + 1 \le 7 \le 9 \le 9$.

The answer is $(5 + 1)^2 + 7^2 + 9^2 + 9^2 = 247$.

Although the partitioning scheme $\{5\}, \{1\}, \{7\}, \{9\}, \{9\}$ has a smaller running time than 247, it is not a valid scheme because $5 \gt 1$.

Although the partitioning scheme $\{5\}, \{1,7\}, \{9\}, \{9\}$ is valid, its corresponding running time is 251, which is larger than 247.

Sample 2 Explanation

The optimal partitioning scheme is $\{5\}, \{6\}, \{7\}, \{7\}, \{4,6,2\}, \{13\}, \{19,9\}$.

Sample 3

See partition/partition3.in and partition/partition3.ans in the contestant's directory.

Data Range

Test Case ID	$n \le$	$a_i \le$	$type =$
$1 \sim 3$	$10$		$0$
$4 \sim 6$	$50$	$10^3$
$7 \sim 9$	$400$	$10^4$
$10 \sim 16$	$5000$	$10^5$
$17 \sim 22$	$5 \times 10^5$	$10^6$
$23 \sim 25$	$1 \times 10^7$	$10^9$	$1$

For all test points with $type=0$, it is guaranteed that the final output answer $\le 4 \times 10^{18}$.

For $100\%$ of the data: $type \in \{0,1\}$, $2 \le n \le 1 \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 \lt 2^{30}$.