Maximum Subarray Sum Modulo

You are given several test cases. For each test case, you are provided with a sequence of N integers, an integer K (the minimum length of a contiguous subarray) and an integer M (the modulo value). Your task is to find the maximum result of calculating the sum modulo M for any contiguous subarray with a length of at least K.

The answer for each test case is computed by considering all contiguous subarrays with lengths in the range \(K \leq L \leq N\), finding the subarray with the maximum sum for that particular length, and then taking the modulo \(M\) of that sum. The final answer is the maximum such modulo among all valid subarrays.

Note: When performing the modulo operation, if the subarray sum is negative, the result should be adjusted so that it lies between 0 and \(M-1\). In most programming languages, the modulo operation on negative numbers may need adjustment.

Example:

• Input: N = 5, K = 3, M = 7, sequence = [1, -2, 3, 4, 5]
• Output: 5

In the above example, among all contiguous subarrays of length at least 3, the maximum sum modulo 7 is 5.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains a single integer \(T\) representing the number of test cases.
2. For each test case:
   1. A line containing three space-separated integers: \(N\) (the number of elements), \(K\) (the minimum length of the subarray), and \(M\) (the modulo value).
   2. A line containing \(N\) space-separated integers representing the sequence.

outputFormat

For each test case, output a single line on stdout containing the maximum subarray sum (of any contiguous subarray of length at least \(K\)) modulo \(M\>.

## sample

5
5 3 7
1 -2 3 4 5
6 2 10
-1 -2 -3 -4 -5 -6
5 2 6
1 2 3 4 5
1 1 3
1
4 2 5
-1 -2 -3 -4

5
9
3
1
4

</p>