Cho một dãy gồm ~N~ (~1 \leq N \leq 10^5~) số nguyên dương ~a_{1}~, ~a_{2}~, ..., ~a_{n}~. Tổng ~a_{i}~ + ~a_{i+1}~ + ...+ ~a_{j}~ (~1 \leq i \leq j \leq N~) được gọi là tổng bộ phận từ ~i~ đến ~j~ của dãy số.

Cho hai số nguyên dương ~P~ và ~K~ (~1 < P \leq 10^{9}~, ~0 \leq K < P~). Hãy tìm tổng bộ phận theo modulo ~P~ nhỏ nhất không bé hơn ~K~.

Ví dụ, xét dãy số sau: ~[12, \, 13, \, 15, \, 11, \, 16, \, 26, \, 11]~

Ở đây ~N = 7~, giả sử ~K = 2~ và ~P = 17~, ta có kết quả là ~2~ vì ~11 + 16 + 26 = 53~ và ~53 \bmod 17 = 2~. Nếu ~K = 0~ ta có kết quả bằng ~0~ vì ~15 + 11 + 16 + 26 = 68~ và ~68 \bmod 17 = 0~.

Input

• Dòng ~1~: ~N~, ~K~, ~P~.
• Dòng 2 đến dòng ~N+1~: ~a_{1}~, ~a_{2}~, ..., ~a_{N}~, mỗi số trên một dòng.

Output

• In ra tổng bộ phận theo modulo ~P~ nhỏ nhất không bé hơn ~K~.

Sample Input

7 2 17
12
13
15
11
16
26
11

Sample Output

2