Description

In 2048, at the exam site of the 30th CSP certification, contestant Xiaoming opened the first problem. The sample of this problem has $n$ groups of testdata, numbered from $1 \sim n$, and the size of the $i$-th testdata is $a_i$.

Xiaoming designed a brute-force program for this problem. For a piece of testdata of size $u$, the running time of the program is $u^2$. However, after the program finishes running on a piece of testdata of size $u$, it will produce wrong results on any piece of testdata whose size is less than $u$. The $a_i$ in the sample are not necessarily increasing, but Xiaoming wants to run the sample correctly without modifying the program. So he decided to use a very primitive solution: divide all testdata into several segments, where the indices within each segment are continuous. Then, merge the testdata within the same segment into new testdata whose size equals the sum of sizes of the original testdata in that segment. Xiaoming will make the sizes of the new testdata non-decreasing.

That is, Xiaoming needs to find some split points $1 \leq k_1 \lt k_2 \lt \cdots \lt k_p \lt n$ such that

$$\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$$

Note that $p$ can be $0$, and in this case $k_0 = 0$, meaning Xiaoming can merge all testdata together and run it once.

Xiaoming hopes that, while running the sample correctly, the running time can be as small as possible, i.e., minimize:

$$\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$$

Xiaoming finds this problem very interesting and asks you for help: given $n$ and $a_i$, please compute the minimum running time of Xiaoming's program under the optimal partition.

Input Format

Because the Constraints of this problem are large, for some test points, $a_i$ will be generated inside the program.

The first line contains two integers $n, type$. The meaning of $n$ is described above, and $type$ indicates the input method.

1. If $type = 0$, then $a_i$ for this test point are given directly. The input then contains: on the second line, $n$ integers $a_i$ separated by spaces, representing the size of each group of testdata.
2. If $type = 1$, then $a_i$ for this test point will be generated specially; the generation method is given later. The input then contains: on the second line, six integers $x, y, z, b_1, b_2, m$ separated by spaces. In the next $m$ lines, the $i$-th line $(1 \leq i \leq m)$ contains three positive integers $p_i, l_i, r_i$ separated by spaces.

For test points $23 \sim 25$ with $type = 1$, $a_i$ are generated 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 \geq 2$. If $n \gt 2$, then for all $3 \leq i \leq n$, $b_i = (x \times b_{i−1} + y \times b_{i−2} + z) \bmod 2^{30}$.

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

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

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

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

Output Format

Output one integer in one line, representing the answer.

5 0
5 1 7 9 9

247

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

1256

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

4972194419293431240859891640

Hint

[Sample 1 Explanation]

The optimal partition is $\{5,1\}, \{7\}, \{9\}, \{9\}$. Since $5 + 1 \leq 7 \leq 9 \leq 9$, this partition is valid.

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

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

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

[Sample 2 Explanation]

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

[Constraints]

::cute-table[]{tuack} | Test Point ID | $n \leq$ | $a_i \leq$ | $type =$ | | :--: | :-: | :-: | :-: | | $1 \sim 3$ | $10$ | $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$ | $4 \times 10^7$ | $10^9$ | $1$ |

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

All test points satisfy: $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 \lt 2^{30}$。

Translated by ChatGPT 5