Longest Contiguous Subarray with Sum Divisible by k

Given a sequence of ( n ) integers and an integer ( k ), find a contiguous subarray whose sum is divisible by ( k ). The goal is to select the longest such subarray and output its length followed by the subarray itself. If there are multiple subarrays with the maximum length, output the one with the rightmost starting index. If no such subarray exists, output ( -1 ).

For example, when ( n = 7 ), ( k = 7 ) and the sequence is: 7 3 4 1 5 14 9:

• The subarrays {7}, {7, 3, 4}, {3, 4} and {5, 14, 9} have sums divisible by \( 7 \).
• The longest subarrays are {7, 3, 4} and {5, 14, 9}; among these, the one with the rightmost starting index is {5, 14, 9}.
• Thus, the output is: 3 on the first line and 5 14 9 on the second line.

Note: All formulas are in \( \LaTeX \) format.

inputFormat

The first line contains two integers ( n ) and ( k ) separated by a space. The second line contains ( n ) integers representing the sequence.

outputFormat

If a valid subarray exists, output two lines: the first line is the length of the subarray, and the second line contains the subarray elements separated by spaces. If no valid subarray exists, output ( -1 ).

sample

7 7
7 3 4 1 5 14 9

3
5 14 9

</p>