PARTSUM  Partial Sums
Given a sequence of positive integers a_{1}, a_{2}, ..., a_{N}, and 1 ≤ i ≤ j ≤ N, the partial sum from
i to j is a_{i} + a_{i+1} + ... + a_{j}.
In this problem, you will be given such a sequence and two integers P and K. Your task is to find the smallest partial sum modulo P that is at least K.
For example, consider the following sequence of integers:
12 13 15 11 16 26 11
Here N = 7. Suppose K = 2 and P = 17. Then, the answer is 2 because 11 + 16 + 26 = 53 and 53 mod 17 is 2. On the other hand, if K = 0 the answer is 0 since 15 + 11 + 16 + 26 = 68 and 68 mod 17 is 0.
You may assume 1 ≤ N ≤ 100000.
Input
The first line of the input contains the number of test cases, T.
Each test case begins with a line containing three integers, N, K and P. This is followed by the values of a_{1}, a_{2}, ..., a_{N}, one per line.
Output
Output one line per test case, containing the smallest partial sum modulo P that is at least K, as described above.
Example
Input: 1 7 2 17 12 13 15 11 16 26 11 Output: 2Warning: large Input/Output data, be careful with certain languages
hide comments
:D:
20100716 09:52:40
You can use 32 bit singed integers for all input data and intermediate calculations. Also you can assume that there always exists at least one sequence meeting the criteria (mod P at leask K) 

Tony Beta Lambda:
20100702 02:49:25
In fact P has an amusing upper bound. P <= 2 ^ 31... 

.:: Pratik ::.:
20090725 15:29:09
What are constraints? (P that is) Last edit: 20090725 15:30:22 
Added by:  Stephen Merriman 
Date:  20070222 
Time limit:  1.510s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  Indian Computing Olympiad, Online Programming Contest, July 06 