Segmented Square Sum Maximization

You are given a non‐decreasing sequence \(\{a_n\}\) of \(n\) integers (i.e. \(a_1 \le a_2 \le \cdots \le a_n\)). For any positive integer \(m\) not exceeding \(k\), you are allowed to partition the sequence into \(m\) consecutive segments (empty segments are allowed). Then, in the \(i\)-th segment (from left to right) you add \(i\) to every number. The modification is done independently for each \(m\) (i.e. the additions do not carry over between different values of \(m\)).

Let the resulting sequence after the addition be \(\{b_j\}\) so that \[ b_j = a_j + f(j),\] where \(f(j)\) is an index assignment satisfying \(1 \le f(1) \le f(2) \le \cdots \le f(n) \le m\). Equivalently, the partition has segments such that in the first segment every element is increased by 1, in the second segment every element is increased by 2, and so on. For a given \(m\), define \(q_m\) as the maximum possible value of \[ \sum_{j=1}^n (a_j + f(j))^2 \] when you choose the partition optimally.

Your task is to compute \[ S = \left(\sum_{m=1}^{k} q_m\right) \bmod 998244353. \]

Note: Since empty segments are allowed, you can effectively assign a value \(f(j)\) to each element such that \(f(1) \le f(2) \le \cdots \le f(n)\) and \(1 \le f(j) \le m\). To maximize \(\sum (a_j+f(j))^2\), it is optimal to assign larger additions to the larger numbers. For instance, if \(m>n\), one optimal strategy is to assign \(f(j)=m-n+j\) for \(1 \le j \le n\>.

For example, consider the sequence \(\{-3,1,2,2\}\) and \(m=5\). Since \(m>n=4\), one optimal assignment is \[ \begin{aligned} f(1)&=5-4+1=2,&b_1&=-3+2=-1,\\ f(2)&=5-4+2=3,&b_2&=1+3=4,\\ f(3)&=5-4+3=4,&b_3&=2+4=6,\\ f(4)&=5-4+4=5,&b_4&=2+5=7.\\ \end{aligned} \] Then \(q_5 = (-1)^2 + 4^2 + 6^2 + 7^2 = 1+16+36+49 = 102.\)

inputFormat

The first line contains two integers \(n\) and \(k\) (1 ≤ n,k). The second line contains \(n\) integers \(a_1,a_2,\dots,a_n\) in non-decreasing order.

outputFormat

Output a single integer: \(S = \left(\sum_{m=1}^{k} q_m\right) \bmod 998244353\).

sample

4 5
-3 1 2 2

102