SP1325 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.

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 one line per test case, containing the smallest partial sum modulo P that is at least K, as described above.