In 2048, at the 30th CSP certification exam, Xiao Ming opened the first problem. The sample for this problem has $n$ sets of data, numbered from $1$ to $n$, where the size of the $i$-th data set is $a_i$.

Xiao Ming designed a brute-force program for this problem. For a data set of size $u$, the running time of this program is $u^2$. However, after this program finishes running on a data set of size $u$, it will produce incorrect results on any data set of size 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. Therefore, he decided to use a very primitive solution: partition all the data into several segments, where the data within each segment is numbered consecutively, and then merge the data within the same segment into a new data set, whose size is equal to the sum of the sizes of the original data in that segment. Xiao Ming will ensure that the sizes of the new data sets are non-decreasing.

That is to say, Xiao Ming needs to find some partition points $1 \le k_1 < k_2 < \dots < k_p < n$ such that:

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

Note that $p$ can be $0$, in which case $k_0 = 0$, meaning Xiao Ming can merge all the data together to run it.

Xiao Ming hopes that while his program runs the sample correctly, the running time is also minimized, 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 + \dots + \left(\sum_{i=k_p+1}^{n} a_i\right)^2$$

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

Input

The input is read from the file partition.in.

Because the data range for this problem is large, $a_i$ for some test cases will be generated within the program.

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

1. If $type = 0$, the $a_i$ for this test case are given directly. The input file continues: the second line contains $n$ space-separated integers $a_i$, representing the size of each data set.
2. If $type = 1$, the $a_i$ for this test case will be specially generated. The generation method is described below. The input file continues: the second line contains six space-separated integers $x, y, z, b_1, b_2, m$. The following $m$ lines each contain three space-separated positive integers $p_i, l_i, r_i$.

For test cases $23 \sim 25$ where $type = 1$, the generation method for $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 > 2$, then $\forall 3 \le i \le n$, $b_i = (x \times b_{i-1} + y \times b_{i-2} + z) \pmod{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 < m$, $p_i < p_{i+1}$.

For all $1 \le j \le m$, if the index $i$ ($1 \le i \le n$) satisfies $p_{j-1} < i \le p_j$, then:

$$a_i = (b_i \pmod{r_j - l_j + 1}) + l_j$$

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

Output

Output to the file partition.out. Output a single integer representing the answer.

Examples

Input 1

5 0
5 1 7 9 9

Output 1

247

Note 1

The optimal partition scheme is $\{5, 1\}, \{7\}, \{9\}, \{9\}$. Since $5 + 1 \le 7 \le 9 \le 9$, this scheme is valid. The answer is $(5 + 1)^2 + 7^2 + 9^2 + 9^2 = 247$. Although the partition scheme $\{5\}, \{1\}, \{7\}, \{9\}, \{9\}$ has a smaller running time than $247$, it is not a valid scheme because $5 > 1$. Although the partition scheme $\{5\}, \{1, 7\}, \{9\}, \{9\}$ is valid, its corresponding running time is $251$, which is greater than $247$.

Input 2

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

Output 2

1256

Note 2

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

Input 3

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

Output 3

4972194419293431240859891640

Input 4

See partition/partition4.in in the contestant directory.

Output 4

See partition/partition4.ans in the contestant directory.

Input 5

See partition/partition5.in in the contestant directory.

Output 5

See partition/partition5.ans in the contestant directory.

Constraints

All test cases satisfy: $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}$.