Anas was thinking about getting his friend and teammate, Majed, a present for his birthday. And who's better at suggesting good birthday presents than codeforces suggesting an array?
Anas decided to gift Majed an array $$$a$$$ of $$$n$$$ integer numbers as codeforces suggested. The cost of a subarray $$$a_l, a_{l+1} \dots a_r$$$ is the sum of its elements modulo $$$m$$$. More formally, the cost of the subarray of $$$a$$$ is $$$(a_l + a_{l+1} + \dots a_r)\ mod\ m$$$.
Majed wrote the cost of all $$$\frac{n \times (n+1)}{2}$$$ subarrays on a whiteboard. He then summed the largest $$$k$$$ numbers on the whiteboard. Can you find that sum?
An array $$$b$$$ is a subarray of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end. In particular, an array is a subarray of itself.
The first line of the input contains a single integer number $$$t$$$ $$$(1 \le t \le 10^4)$$$. The number of test cases.
The first line of each test case contains three space-separated integer numbers $$$n$$$, $$$m$$$ and $$$k$$$ $$$(1 \le n \le 10^5, 1 \le m \le 10^5, 1 \le k \le min(\frac{n \times (n+1)}{2}, 10^9))$$$.
The second line of each test case contains $$$n$$$ space-separated integer numbers $$$a_1, a_2 \dots a_n$$$ $$$(1 \le a_i \le 10^9)$$$.
It is guaranteed that the sum of $$$n$$$ over all of the test cases does not exceed $$$10^5$$$.
For each test case print a single line containing a single integer number. The sum of the largest $$$k$$$ numbers in the whiteboard.
34 4 41 2 3 45 2 109 4 16 7 29 8 155 66 1 3 7 6 32 17 8
11 9 86
In the first test case, $$$a=[1, 2, 3, 4]$$$. The subarrays are:
$$$- [1]$$$ The sum of the elements of the subarray is $$$1$$$. The cost of the subarray is $$$1\ mod\ 4 = 1$$$.
$$$- [1, 2]$$$ The sum of the elements of the subarray is $$$3$$$. The cost of the subarray is $$$3\ mod\ 4 = 3$$$.
$$$- [1, 2, 3]$$$ The sum of the elements of the subarray is $$$6$$$. The cost of the subarray is $$$6\ mod\ 4 = 2$$$.
$$$- [1, 2, 3, 4]$$$ The sum of the elements of the subarray is $$$10$$$. The cost of the subarray is $$$10\ mod\ 4 = 2$$$.
$$$- [2]$$$ The sum of the elements of the subarray is $$$2$$$. The cost of the subarray is $$$2\ mod\ 4 = 2$$$.
$$$- [2, 3]$$$ The sum of the elements of the subarray is $$$5$$$. The cost of the subarray is $$$5\ mod\ 4 = 1$$$.
$$$- [2, 3, 4]$$$ The sum of the elements of the subarray is $$$9$$$. The cost of the subarray is $$$9\ mod\ 4 = 1$$$.
$$$- [3]$$$ The sum of the elements of the subarray is $$$3$$$. The cost of the subarray is $$$3\ mod\ 4 = 3$$$.
$$$- [3, 4]$$$ The sum of the elements of the subarray is $$$7$$$. The cost of the subarray is $$$7\ mod\ 4 = 3$$$.
$$$- [4]$$$ The sum of the elements of the subarray is $$$4$$$. The cost of the subarray is $$$4\ mod\ 4 = 0$$$.
The costs of all subarrays are $$$0, 1, 1, 1, 2, 2, 2, 3, 3, 3$$$. The sum of the costs of the $$$4$$$ largest cost subarrays is $$$2+3+3+3=11$$$.
