Prefix - 4
Problem
Given a sequence of
N numbers. Find the minimum sum of all elements of a sequence's own prefix whose sum of all elements of the prefix, when divided by
K , has the same remainder as the sum of all elements of the given sequence. If there are several such prefixes, determine the one with the shorter length. Print the length of such a prefix. It is guaranteed that such a prefix exists.
Input
The first line contains two numbers: the number of numbers in the sequence
N (1 <= N <= 10
8) and the number
K ( 1 <= K <= 100). Next comes
N lines, one integer per line. Each number does not exceed
10000.
Imprint
Display the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
5 2
2
-2
2
-2
2 |
2 |