Prefix - 2
Problem
Given a sequence of
N natural numbers. Find the minimum length of a proper sequence 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. 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 natural number per line. Each number does not exceed
10000.
Imprint
Display the answer to the problem.
Examples
| # |
Input |
Output |
| 1 |
5 3
33
41
18
23
40 |
2 |